Nikitin Roman - 5 months ago 35
C++ Question

# Find the modulo of division of very big numbers

I have to find the modulo of division of this numbers:

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

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

... etc up to 1001;

Using only native libraries in c++. How to do that? As you can see, the first number is about 3 billion symbols.

I tried finding the length of modulo periods, but they are mush longer, than 10, and even

`unsigned long long int`
can't deal with such big numbers (239^10). Also I think that "big numbers" algorithms (storing a number as an array) will not work for me too (500*10^9) is too much operations.

BTW, this is supposed to work less, than 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 we can do it recursively.

So, here is 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;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download