# 数论-逆元

数论-逆元

目录

• 数论-逆元
  • 费马小定理+快速幂求逆元
  • 扩展欧几里得(难写，但是常数比费马小)
  • 线性递推求逆元
    • 求1-n的逆元(O(n))
    • 1!-n!的逆元

费马小定理+快速幂求逆元

• (frac{1}{a}\%p=a^{p-2}\%p)(p为质数，且a和p互质),使用快速幂复杂度(O(log)  $ p)$

LL qpow(LL a,LL b){
    LL ans=1;
    a=a%p;
    while(b){
        if(b&1)
    }
}

LL inv(LL a){
    return qpow(a,p-2);
}

扩展欧几里得(难写，但是常数比费马小)

typedef  long long ll;
void extgcd(ll a,ll b,ll& d,ll& x,ll& y){
    if(!b){ d=a; x=1; y=0;}
    else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
ll inv(ll a,ll n){
    ll d,x,y;
    extgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}

线性递推求逆元

求1-n的逆元(O(n))

• 公式:inv[i]=((mod-mod/i)*inv[mod%i])%mod

inv[1] = 1;
for (int i = 2; i <= MAXN; i++) 
    inv[i]=((mod-mod/i)*inv[mod%i])%mod;

1!-n!的逆元

• 公式: inv[i] ≡inv[i+1]*(i+1) (mod p)，使用费马小定理求出最大阶乘的逆元，再往回推