I am having trouble in understanding how this code is giving the correct answer for larger test cases (TL > limit of long long int). Suppose `TL = 83478347589347598347598347598347983475983475983475893475983475893475`

and `N = 348573894578934759834759834759834798327498237498237498237498327482397492384`

, the above code will give `a = 159184929`

and `b = 749176548`

. Now we’ll calculate `a^b % MOD`

instead of directly calculating `TL^N % MOD`

. How is `a^b % MOD`

== `TL^N % MOD`

?

2 Likes

U can go through “Fermat’s Little Theorem”…hope this will help…

1 Like

I understood the part where he takes A as a string input and then did a=(a*10+(A[i]-‘0’))%1000000007;. You can express (a * b)MOD as ((A MOD) * (B MOD) ) MOD. So he makes a = TL % MOD since it does not affect whether you take MOD before or after multiplication. @kunal361 I dont know much about Fermat’s theorem. Could you briefly explain how to apply it here. Does it require that N be of the form prime-1?

1 Like

According to Fermat’s Little Theorm, A^ (p-1) ≡ 1 p , where p is a prime number.
Hence we take B(p-1) => B%(10^9+6).

Now we have two 9 digit numbers which we solve using fast exponentiation.

2 Likes