The question says, given A,N,P find A(N!) %P.
So i am calculating A1%P, A2%P, . . . , AN%P
then multiplying them all together to get the desired A(N!) %P, but for some test cases it is showing WA.
My Code : m4xqJG - Online C++0x Compiler & Debugging Tool - Ideone.com
Can you share the problem link? So that I can know the constraints
What you are calculating is different from what is required. You are calculating A^1\cdot A^2 \cdot A^3 \ldots A^N = A^{1 + 2 + 3 \ldots N} = A^{\frac{N^2+N}{2}}\neq A^{N!}
Calculate e = N! mod phi ( p ) where phi is Euler’s totient function
If p is prime, \phi( p ) = p-1
Answer would be A^e \pmod p
You can calculate that using Modular Exponentiation
You are calculating A^(N*(N+1)/2) but you need to calculate A^(N!)%P.
Try using Euler’s phi function to solve this…by calculating temp = N!%(phi§) first and then A^temp%p to get what you want.
Can u explain the concept of Euler phi function here, and how to understand this.
@ssrivastava990
I have used the following property:
If A is co-prime to p and \phi(p) is the number of numbers less than p and co-prime to p then, A^{\phi(p)} \equiv 1 \pmod p. The proof can be found here
We can write any number k as k = q\cdot \phi(p) + r where \displaystyle q = \left \lfloor\frac{k}{\phi(p)} \right\rfloor and r = k \% \phi(p)
Then, \displaystyle A^k = A^{q\cdot \phi(p) + r} = A^{q\cdot \phi(p)}\cdot A^{r} = \left ( A^{q} \right )^{\phi(p)}\cdot A^{r}
Since A is co-prime to p, A^q is also co-prime to p \therefore \left ( A^{q} \right )^{\phi(p)} \equiv 1 \pmod p
\therefore A^k \equiv A^{k \% \phi(p)} \pmod p
If you are unfamiliar with the mod notation read this