Nikitin Roman - 27 days ago 9

C++ Question

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`

BTW, this is supposed to work less, than in 5 hours.

Answer Source

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;
}
```