求逆元

相关定理

1. 费马小定理，有$n^{p-1} \equiv 1 (mod p)$。 因此$\frac{1}{n} \equiv n^{p-2} (mod p)$

2. 方程$ax \equiv1(mod n)$的解被称为a关于模n的逆，当$a<n$且$gcd(a,b)=1$时方程有唯一解:$x=a^{n-2}modn$

   例如: $x=\frac{5}{2}modp$可以转化为$x=5*2^{p-2}\%p$

求逆元方法:

通过扩展欧几里得算法求逆元

// when we used this method to calculate x / y % p, we also need x and p is coprime 
// Method 1:     Extended Euclid
// Requires:    a and b is coprime
// Modify:      x, y
// Effects:     when the method is finished, x is a's inverse element about b.
// Return:      gcd(a, b)

int ex_gcd(int a, int b, int &x, int &y) {
    int ret, tmp;
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ret = ex_gcd(b, a % b, x, y);
    tmp = x;
    x = y;
    y = tmp - a / b * y;
    return ret;
}

通过递推求1~n的逆元

$inv[i] = (p - \frac{p}{i})* inv[p \% i] \% p$

这个算法可以在O(n)O(n)的时间复杂度内求出n以内所有数的逆元，不过需要注意的是p必须为奇质数。

// when we used this method to calculate x / y % p, we also need x and p is coprime
// Method 3:    Recursive to get i's inverse element
// Requires:    p is prime and p != 2
// Modify:      inv[]
// Effects:     inv[i] is i's inverse element about p;

int inv[N];
void get_inverse(int n, int p) {
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = (p - p / i) * inv[p % i] % p;
    }
}

阶乘的逆元:

$invf[i] = invf[i + 1] * (i + 1) \% p$

// when we used this method to calculate x / y % p, we also need x and p is coprime
// Method 4:    Recursive to get Factorial[i] and their inverse element
// Requires:    p is prime
// Modify:      invf[], factor[]
// Effects:      factor[i] is i's factorial, invf[i] is factor[i]'s inverse element

int invf[N], factor[N];
void get_factorial_inverse(int n, int p) {
    factor[0] = 1;
    for (int i = 1; i <= n; ++i) {
        factor[i] = i * factor[i - 1] % p;
    }
    invf[n] = quick_inverse(factor[n], p);
    for (int i = n-1; i >= 0; --i) {
        invf[i] = invf[i + 1] * (i + 1) % p;
    }
}

HDU5698 瞬间移动(求逆元)

我们要从$(1,1)$点走到$(n,m)$点，只能向右下角的格子里走，那么$(1,1)$所在的行和列不能走,$(n,m)$所在的行和列不能走，那么能走的面积就是$(n-2)*(m-2)$这么大的面积，行和列分别考虑，实质上就是求组合数$C_{(n-2)+(m-2)}^{n-2}$

因为$C_n^m=\frac{n!}{m!*(n-m)!}$,乘以一个数等于乘这个数的逆元，我们先预处理出阶乘的逆元。

首先求出一个数模p的逆元: $f[i]=(p-\frac{p}{i})*f[p\%i]\%p$ 然后再递推出$n!$的逆元 $inv[(n-1)!]=inv[n!]*n\%p$ 可以得到 $inv[n!]=inv[(n-1)!]*f[n]\%p$

然后就可以求出组合数了

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll N=200000+20;
ll fac[N]= {1,1},inv[N]= {1,1},f[N]= {1,1};
/*
fac[i]:i的阶乘
inv[i]:i的阶乘的逆元
f[i]:i的逆元
*/
ll C(ll a,ll b)//除以一个数等于乘这个数的逆元
{
    return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
void init()
{
    for(ll i=2; i<N; i++)
    {
        fac[i]=fac[i-1]*i%mod;
        f[i]=(mod-mod/i)*f[mod%i]%mod;
        inv[i]=inv[i-1]*f[i]%mod;
    }
}

int main()
{
    ll n,m;
    init();
    while(cin>>n>>m)
        cout<<C(m+n-4,m-2)<<endl;
    return 0;
}