【洛谷P3811】[模板]乘法逆元

乘法逆元

题目链接

求逆元的三种方式：

1.扩欧

i*x≡1 (mod p)

可以化为：x*i+y*p=1

exgcd求x即可

inline void exgcd(int a,int b,int &x,int &y){

    if(b==){

        x=; y=;

        return;

    }

    exgcd(b,a%b,x,y);

    int t=x;

    x=y;

    y=t-(a/b)*y;

}

2.快速幂

费马小定理：a^(p-1) ≡ 1 (mod p)

a*a^(p-2)≡1(mod p)

x=a^(p-2) 即为逆元

inline int qpow(int x,int k){

    int s=;

    while(k){

        if(k&) s=s*x%p;

        k>>=;

        x=x*x%p;

    }

    return s;

}

3.线性递推：

inv[i]=(M-M/i)*inv[M%i]%M;

证明：

设t=M/i,k=M mod i

t*i+k≡0(mod M)

t*i≡-k(mod M)

两边同时乘以k和i的逆元：t*inv[k]≡-inv[i](mod M)

inv[i]≡-t*inv[k](mod M)

将t和k用M和i表示：

inv[i]≡(-M/i)*inv[M mod i](mod M)

 

inv[]=;for(int i=;i<=n;i++)

     inv[i]=(p-p/i)*inv[p%i]%p;