逆元的求法

1.扩展欧几里得：

   

void Exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) x = 1, y = 0;
    else Exgcd(b, a % b, y, x), y -= a / b * x;
}
int main() {
    ll x, y;
    Exgcd (a, p, x, y);
    x = (x % p + p) % p;
    printf ("%d
", x); //x是a在mod p下的逆元
}

2.费马小定理+快速幂：

ll fpm(ll x, ll power, ll mod) {
    x %= mod;
    ll ans = 1;
    for (; power; power >>= 1, (x *= x) %= mod)
        if(power & 1) (ans *= x) %= mod;
    return ans;
}
int main() {
    ll x = fpm(a, p - 2, p); //x为a在mod p意义下的逆元
}

 3.线性递推方程：

$k∗i+r≡0(modp)$

$k∗(r的逆元)+(l的逆元)≡0(modp)$

$(l的逆元)≡−k∗(r的逆元)(modp)$

$(l的逆元)≡−⌊p/i​⌋∗((p%i)的逆元)(modp)$

#include <bits/stdc++.h>
#define p 1000000007
using namespace std;
long long inv[100010];
int main()
{
	int n;
	cin>>n;
	inv[1]=1;
	for(int i=2;i<=n;i++){
		 inv[i]=(p-p/i)*inv[p%i]%p;
	}
	for(int i=1;i<=n;i++){
		cout<<inv[i]<<" ";
	}
}

另外，对于阶乘：inv[i+1]*(i+1)=inv[i]