dreamoon_love_AA's blog

Share a method to find the multiplicative inverse of 1~n mod p
By dreamoon_love_AA, 12 years ago, In English

Firstly, we denote the multiplicative inverse of x mod p as inv(x,p).

  1. use dp method to calculation x! mod p for x=1 ~ n (1<=n<p, p is some prime)
  2. calculate inv(n!,p) utilize Extended Euclidean algorithm.
  3. use dp again to calculate inv(x!,p) for x=n-1 ~ 1 with the fact inv(x!,p) * x = inv((x-1)!, p)
  4. now, if we want to now inv(x,p) for some x in [1,n], we only need to calculate (x-1)! * inv(x!,p)
  • Vote: I like it
  • +38
  • Vote: I do not like it

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

Or just do the following:

inv[1] = 1;
for (int i=2; i<p; ++i)
	inv[i] = (p - (p/i) * inv[p%i] % p) % p;
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great! I've seen that approach once before and since then I was trying to find it again. It's some kind of magic, but I'm going to understand how that works...

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Maybe this will help :)

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +12 Vote: I do not like it

      It's quite easy to explain how it works. Let's take simple equation and do some transformations with it:

      p % i = p - (p / i) * i
p % i = -(p / i) * i (mod p) // divide by i * (p % i)
inv[i] = - (p / i) * inv[p % i]

      UPD: too slow

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it -21 Vote: I do not like it

        but doesnt a muplicative inverse of x mod p only exist when gcd(x,p) == 1,how do you find the muplicative inverse of a range if some of them dont exist

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          We can only use this approach if we have prime modulo p and want to calculate inverse in range [1, p).

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

    i have seen this approach in rng_58's solution.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +44 Vote: I do not like it

    I know that this is like 6 years old, but this post shows up a lot on Google, and I wanted to mention that you can omit the last % p.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Challange: p = 113513 look at the value of inv[3] :)

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        That's just because the multiplication between p/i and inv[p%i] overflows, I think.

        If so, another good warning for future searches is: Don't forget to declare inv as a long long array (or cast to a long long before multiplying)!

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

2. calculate inv(x!,p)
Do you mean inv(n!,p)?
we only need to calculate (x-1)! * inv(x,p)
Do you mean (x-1)! * inv(x!,p)?

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

Nice method! The also exists O(NloglogN) dp solution, which is slower, but seems to be very easy to implement. Let f[x] be the smallest prime, which divides x. We can calculate f[x] for all x in range 1...n using sieve of Eratosthenes. Then we can calculate inv[x] using formula inv[x]=(inv[x/f[x]]*inv[f[x]])%mod.

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Is the following function correct to calculate nCr? ( n Choose r )

i64 nCr(i64 n,i64 r)
{
    i64 c=(inv[r]*inv[n-r])%modL;
    return (fac[n]*c)%modL;
}

(inv[x] is Modular Multiplicative Inverse of x!(x factorial) and fac[x] is x!. i64 is macro of long long. modL is large prime number.)

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

    Yes it is.

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

      (((333333336*500000004)%1000000007)*120)%1000000007 is 20.

      I tried to calculate 5C2 and found it 20 from this function.

      333333336 is inverse modulus of 3
500000004 is inverse modulus of 2
120 is factorial of 5
1000000007 is a prime number

      The correct output is 10.

      this and this sites are used for calculation.

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

        Well you don't need inverse of 3 and 2 you need the inverse of 3! = 6 and 2! = 2 (because nCr is equal to n! / ( r! * (n — r)! ) so 5C2 is ( 5! * inverse[6] * inverse[2] ) % 1000000007 = ( 120 * 166666668 * 500000004 ) % 1000000007 = 10.

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

sorry, i wrote this under wrong blog announcement

→ Reply