Блог пользователя akash_goel

Автор akash_goel, история, 9 лет назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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).

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Unable to parse markup [type=CF_TEX]

.