Chef and Pattern

general
,
1

hey guys ,
Can you please help me in proving that (k^(2^n))%MOD is equailvalent to (k^((2^n)%(MOD-1))%MOD?
Thanks,

2

It comes from Fermat’s Little theorem…

check this thread for proof : click here

1 Like
3

I tried the following,
a = (2^n-3)%MOD [ n<=2 taken care manually]

ans = (k^a)%MOD;
But it gives WA… Why is that??

4

If you look in closely a was infact at max 2^(1e9) so that large a value will not be taken care by any language(a will overflow, so you have to mod a then k^a%MOD) , so you had to use the formuale mentioned above in my post.