定义

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

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

求解逆元的方式

拓展欧几里

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

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

ax1 mod max \equiv 1\ mod \ m

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

推导过程

ax=by+1ax%b=11 %b=1}ax1 (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为质数,还可以根据费马小定理求逆元

ap11(mode p)a^{p-1} \equiv1(mode\ p),此时逆元x可取为ap2%pa^{p-2}\%p

线性求逆元

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

11=1,i>=21^{-1}=1,\forall i>=2,i1=(ppi)×(p%i)1i^{-1}=(p-\frac{p}{i})\times(p\%i)^{-1}

证明

p=ki+r,r<i,i<i<pp=k\cdot i+r,r < i,i < i < p

{0modp=0ki+rmodp=0ki+r0(modp)\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)

将两边同除i1r1i^{-1}\cdot r^{-1}

得到 kr1+i10(modp)k\cdot r^{-1}+i^{-1}\equiv0(\mod p)

i1=kr1i^{-1}=-k\cdot r^{-1}

i1pi(pmodi)1(modp)i^{-1}\equiv-\lfloor \frac{p}{i}\rfloor\cdot(p\mod i)^{-1}(\mod p)

dp[i]=i1dp[i]=i^{-1}

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

常见用途

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

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

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)