c++ - Find the modulo of division of very big numbers -


i have find modulo of division of numbers:

239^(10^9) , 10^9 + 13

239^(10^9) , 10^9 + 15

... etc 1001;

using native libraries in c++. how that? can see, first number 3 billion symbols.

i tried finding length of modulo periods, mush longer, 10, , unsigned long long int can't deal such big numbers (239^10). think "big numbers" algorithms (storing number array) not work me (500*10^9) operations.

btw, supposed work less, in 5 hours.

we know that:

(a*b) % mod = ((a % mod) * (b % mod)) % mod 

so

(a^n) % mod = (((a ^ (n/2)) % mod) * ((a ^ (n/2)) % mod)) % mod; 

and can recursively.

so, here our function:

int cal(int pow, int val, int mod){    if(pow == 0)       return 1;    int v = cal(pow/2, val, mod);    if(pow % 2 == 0)       return (v*v) % mod;     else       return (((v*val) % mod) * v) % mod; } 

Comments

Popular posts from this blog

c++ - Difference between pre and post decrement in recursive function argument -

php - Nothing but 'run(); ' when browsing to my local project, how do I fix this? -

php - How can I echo out this array? -