akash_goel's blog

Help needed to understand problem 559C
By akash_goel, history, 9 years ago, In English

Here is the link — http://mirror.codeforces.com/problemset/problem/559/C This is similar to this — https://www.codechef.com/CDCRF15R/problems/CWAYS/

In the solutions, I can see inverse factorial being calculated as 

inv(n) = pow(n,mod-2)

I don't get where the mod-2 value comes from. Can someone please explain?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

This is because pow(n, p - 1) = 1(modp) holds (Fermat's Little Theorem).

So pow(n, p - 2) * n = 1(modp) also holds, and it means inv(n) = pow(n, p - 2).

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

Due to Fermat's little theorem, if p = 109 + 7 is prime then

Unable to parse markup [type=CF_TEX]

.
→ Reply