POWPOW2 - SPOJ Number THeory

#1

Here, I didn’t get how he changed y from 2nCn to k$(m)+(y%$(m)). In a nutshell, how did he convert y into desired form?

#2

@aiman.mumtaz
We use totient function to reduce the problem, into a more simple problem.
We know that if m is prime phi(m)=m-1.
Now for some number y, we can write it as, y=k(m-1) + y%(m-1) (we can always break down a number like thi, let m=11, we can write 33= 3*(11-1) + (33%(11-1)));
(Any number can always be written as a= x z + a%x, mathematical property can prove with little effort)
Now if y<(m-1) k will become zero. else it will be greater than 1, But its does not affect us as
a^(k (m-1)+rem)=(a^(m-1)K )a^rem.
Now focus on (a^(m-1)K) = a^(m-1) * a^(m-1) * a^(m-1) … k times (simple exponentiation rule)
now we know. a^(m-1)%m=1 , so our term (a^(m-1)K)= 11*1…=1

Se we never needed the value of K
If this resolves your doubt mark it resolved.