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
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.
3 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
can you send me its code ??