### dreamoon_love_AA's blog

By dreamoon_love_AA, 8 years ago,

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)

• +38

 » 8 years ago, # |   +12 Or just do the following: inv[1] = 1; for (int i=2; i
•  » » 8 years ago, # ^ |   0 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...
•  » » » 8 years ago, # ^ |   +5 Maybe this will help :)
•  » » » » 6 months ago, # ^ |   -22 Thanks, it helped a lot
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +12 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
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   -21 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
•  » » » » » 11 months ago, # ^ | ← Rev. 2 →   0 We can only use this approach if we have prime modulo p and want to calculate inverse in range [1, p).
•  » » » » » » 11 months ago, # ^ |   0 got it,thank you
•  » » 8 years ago, # ^ |   0 i have seen this approach in rng_58's solution.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +44 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.
•  » » » 2 years ago, # ^ |   -6 Challange: p = 113513 look at the value of inv[3] :)
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +6 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)!
 » 8 years ago, # |   0 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)?
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Yes, you are right. :p Now I fix it.
 » 8 years ago, # |   0 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.
•  » » 8 years ago, # ^ |   +3 If write good sieve of Eratosthenes, it works O(n).
•  » » » 8 years ago, # ^ |   0 Yes, you are right.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 Can you share your most optimized code about sieve Eratosthenes?
 » 8 years ago, # |   +8 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.)
•  » » 8 years ago, # ^ |   0 Yes it is.
•  » » » 8 years ago, # ^ |   0 (((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.
•  » » » » 8 years ago, # ^ |   0 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.
•  » » 8 years ago, # ^ |   0 Since, r! and (n-r)! both are denominator, I'm confused whether following operation is valid or not. i64 c=(inv[r]*inv[n-r])%modL;
 » 3 months ago, # | ← Rev. 2 →   -19 sorry, i wrote this under wrong blog announcement