POWPOW2(Hard), Spoj Number Theory

#1

why did we checked if b is even or odd
while computing b^(2nCn) % (10^9+6)

#2

hi @dedeomkar,
Suppose b is odd. Then, we can apply Euler’s theorem because b and 1,000,000,006 are coprime
if b is even, b and 1000000006 are not coprime, so need CRT again. here modulus is the product of two primes: 2 and 500,000,003. So you need to find and and use CRT to get the result modulo 1,000,000,006.

#3

Thanks @talhashamim001

That makes sense, however I do not see this logic being used in the code:

Capture
Capture1245×905 184 KB

#4

@dedeomkar,
during discussion prateek bhaiya said na its one of the trick you can use but the later case generalizes both

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.