asif599's blog

Calculating pow(a,nCr) % p
By asif599, history, 9 years ago, In English

Hello Codeforces How to calculate pow(a,nCr) % p efficiently? Here 1 <= n <= 10^6, 1 <= r <= 10^6 and 1<= a <= 10^6

  • Vote: I like it
  • -4
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Sorry, i got it wrong

→ Reply
»
9 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Hint: Use Legendre's formula and Fermat's little Theorem.

→ Reply
»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

To find a^b %m when b is too large, we calculate a^(b%(m-1))%m this can be proceed using fermat little theorem.

To calculate nCr%(m-1) you can use chinese remainder theorem if m-1 is non prime and square free.

→ Reply
  • »
    »
    9 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I prove a^b %m= a^(b%(m-1))%m in this way, but I am not sure whether it is correct or not.

    Fermat's little theorem tells that a^(m-1) %m=1, and thus we can write b=x*(m-1)+y. Then, a^b %m=a^(x*(m-1)+y) %m= a^y * (a^(m-1))^x %m= (a^y %m) * (a^(m-1) %m)^x=a^y %m =a ^ (b%(m-1)) %m.

    If this is correct, I really have never considered using Fermat's little theorem in this manner... My first reaction is to calculate the inverse of b when we need to compute a/b %m. Thank you so much for sharing such wonderful idea and extending my thought.

    → Reply
  • »
    »
    9 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Can you elaborate more on how you calculte nCr%(m — 1) using chinese remainder theoreom ? Suppose that (m — 1) is non-prime.

    → Reply