跳到主要内容

2023/04/乘法逆元

· 阅读需 2 分钟
小鱼干
小鱼干
干饭人

定义​

ax≡1 mod pa x \equiv 1\ mod \ p这里xx就是aa的逆元。

一个数有逆元的充分必要条件是gcd(a,p)=1，此时逆元唯一存在。

求解逆元的方式​

拓展欧几里​

若m不为质数，可以使用拓展欧几里得求逆元

根据裴蜀定理，若gcd(a,b)=1则gcd是a,b两个数线性组合的最小值，其他组合都是gcd的倍数。

ax≡1 mod max \equiv 1\ mod \ m。

gcd(a,b)=1，满足ax+by=1ax+by=1,移项得ax=−by+1ax=-by+1，即ax≡1 mod bax\equiv1 \ mod \ b，此时的x就是逆元。实际上线性不定方程组有无穷多解，这里只求正的最小逆元。

推导过程

ax=−by+1⇒ax%b=11 %b=1}⇒ax≡1 (mod b)ax=-by+1\Rightarrow \left. \begin{aligned} ax \%b&=1 \\ 1 \ \%b&=1 \\ \end{aligned} \right\}\Rightarrow ax\equiv1 \ (mod\ b)

扩欧代码

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int z=x;x=y;y=z-y*(a/b);
    return d;
}

ans=(x%b+b)%b;//x可能是负数，需要处理

费马小定理​

若模数p为质数，还可以根据费马小定理求逆元

若p为质数,gcd(a,p)=1gcd(a,p)=1，则有ap−1≡1(mod   p)a^{p-1}\equiv 1(\mod\ p) .

a×ap−2≡1(mod  p)a\times a^{p-2}\equiv 1(\mod p)

ap−1≡1(mode p)a^{p-1} \equiv1(mode\ p)，此时逆元x可取为ap−2%pa^{p-2}\%p。

线性求逆元​

模数p为质数，可在线性时间推出1∼n1\sim n的所有逆元。

1−1=1,∀i>=21^{-1}=1,\forall i>=2,i−1=(p−pi)×(p%i)−1i^{-1}=(p-\frac{p}{i})\times(p\%i)^{-1}

证明

设p=k⋅i+r,r<i,i<i<pp=k\cdot i+r,r < i,i < i < p

{0mod  p=0k⋅i+rmod  p=0⇒k⋅i+r≡0(mod  p)\left\{\begin{aligned} 0 \mod p &=0\\ k\cdot i +r \mod p &=0 \end{aligned}\right. \Rightarrow k\cdot i +r\equiv0(\mod p)

将两边同乘i−1⋅r−1i^{-1}\cdot r^{-1}

得到 k⋅r−1+i−1≡0(mod  p)k\cdot r^{-1}+i^{-1}\equiv0(\mod p)

i−1=−k⋅r−1i^{-1}=-k\cdot r^{-1}

i−1≡−⌊pi⌋⋅(pmod  i)−1(mod  p)i^{-1}\equiv-\lfloor \frac{p}{i}\rfloor\cdot(p\mod i)^{-1}(\mod p)

i−1%p=(−⌊pi⌋)%p⋅(pmod  i)−1%pi^{-1}\%p = (-\lfloor \frac{p}{i}\rfloor)\%p\cdot(p\mod i)^{-1}\%p

i−1%p=(−pi+p)%p⋅(pmod  i)−1%pi^{-1}\%p = (- \frac{p}{i}+p)\%p\cdot(p\mod i)^{-1}\%p

设dp[i]=i−1dp[i]=i^{-1}

由上可得出 dp[i]=(p-p/i)*dp[p%i]

常见用途​

将对结果取余的较大数字的除法，转成乘法进行计算。

a/b(mod  p)=a×b−1(mod  p)a/b(\mod p)=a\times b^{-1}(\mod p)