Calculating (a^b)%MOD
c++, math
Solution
That's a typical task. Please (or, really, PLEASE!) read about the Euler's totient function.
And then the Euler's theorem.
The thing is you can dramatically reduce a^b to a^(b % phi(MOD)). Yes, you will need some kind of an integer factorization method, but still, no crazy ideas about actually calculating the power needed.
We did such samples by hand in my youth :) Even when the numbers where far beyond 32/64 bit range.
EDIT: Well, you live and learn. In 2008 the result is obtained:
"The totient is the discrete Fourier transform of the gcd: (Schramm (2008))"
So to calculate phi(b) one does not need to know its factors.
EDIT(2):
And the Carmichael's function is what you need to calculate to get the correct answer for any a, b and MOD.
Problem
I want to code for calculating the value of pow(a,b)%MOD. I use C++ to code. But the problem is the value of b can be very large. I know the log(b) time complexity method. But, the value of b might not fit in the data type "long long" of C++. For example b can be 1000000000 th Fibonacci number. Exact calculation of such a big number is itself, not possible (in time limits). P.S. : - pow(a,b) means a*a*a*a*... b times. - X % MOD means the remainder obtained on dividing X by MOD.