How to handle things when we want to calculate pow(a,b) where a and b are really huge.
By really huge, I mean a is order of pow(10,1000).
1 Like
Input it digit wise and calculate a%p, b%(p-1), and then calculate.
Ok by digit wise do you mean as a string?
can i replace a^b by (a%p)^(b%(p-1))?
But why can you elaborate a little more?
It would be really helpful.
You can so a%p because
(k_1p+a)(k_2p + b) has only one term that is 0 mod p ab. For b\%(p-1) , this is true because of fermats little theorem.
If the answer to an exponential term is quite big, most problems would ask you to return the answer mod something.
In that case, you can use modular exponentiation.
1 Like
Basically my doubt is say I have a very large number say A=2 ^x where x is itself 10^10000 and we want to find a power of A which satisfies a given condition…
In short I need log(B)/log(A) (given log(B)/log(A) is a perfect integer i.e. B is some power of A)
My final ans is log(B)/log(A).