Exercise

Big Mode

#include<stdio.h>
int bigmod(int a, int b, int m);
int main(){
    int a = 5, b = 15, m = 6;

    printf("%d\n", bigmod(a, b, m));

    return 0;
}

int bigmod(int a, int b, int m){
    int x;
    if(b==0){
        return 1;
    }
    if(b%2==1){
        x = bigmod(a, b-1, m);
        return (a*x) % m;
    }else{
        int x = bigmod(a, b/2, m);
        return (x*x) % m;
    }
}

Power

#include<stdio.h>
int power(int a, int b, int m);
int main(){
    printf("%d",power(3, 5, 4));
    return 0;
}

int power(int a, int b, int m){
    if(b==0){
        return 1;
    }
    else if((b&1)==1){
        return (power(a,b-1,m) * a) % m;
    }else{
        int x = power(a,b/2,m) % m;
        return (x*x)%m;
    }
}