Firstly, we denote the multiplicative inverse of x mod p as inv(x,p).
- use dp method to calculation x! mod p for x=1 ~ n (1<=n<p, p is some prime)
- calculate inv(n!,p) utilize Extended Euclidean algorithm.
- use dp again to calculate inv(x!,p) for x=n-1 ~ 1 with the fact inv(x!,p) * x = inv((x-1)!, p)
- 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)
Or just do the following:
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...
Maybe this will help :)
It's quite easy to explain how it works. Let's take simple equation and do some transformations with it:
UPD: too slow
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
We can only use this approach if we have prime modulo p and want to calculate inverse in range [1, p).
i have seen this approach in rng_58's solution.
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.Challange: p = 113513 look at the value of inv[3] :)
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)!
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)?
Yes, you are right. :p Now I fix 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.
If write good sieve of Eratosthenes, it works O(n).
Yes, you are right.
Can you share your most optimized code about sieve Eratosthenes?
Is the following function correct to calculate nCr? ( n Choose r )
(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.)
Yes it is.
(((333333336*500000004)%1000000007)*120)%1000000007 is 20.I tried to calculate 5C2 and found it 20 from this function.
The correct output is 10.
this and this sites are used for calculation.
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.
sorry, i wrote this under wrong blog announcement