【数学】逆元

逆元

前置知识

单位元

在一个集合中，对于某种运算，如果对于任何的集合元素 a，和元素 e 运算，得到还是集合元素 a 本身，则称 e 为这个运算下的单位元。

在加法运算中，对于任意实数\(a\)，有\(a+e=e+a=a\)，则单位元\(e=0\) (可以认作相反数)

在乘法运算中，对于任意实数\(a\)，有\(a\times e=e\times a=a\)，则单位元\(e=1\) (可以认作倒数)

模乘的单位元是\(1(\bmod n)\) (证明自己搜)

逆元

在一个集合中，对于某种运算 ，如果任意两个元素的运算结果等于单位元，则称这两个元素互为逆元。

模意义下的乘法逆元

若\(ax\equiv 1(\bmod p)\) 且\(\gcd(a,p)=1\)(a与p互质)，则称a关于模p的乘法逆元为x

逆元即数论中的广义倒数。

费马小定理

若p为质数，则\(\gcd(a,p)=1\)，则\(a^{p-1}\equiv 1(\bmod p)\)

或对于任意整数a，有\(a^p\equiv a(\bmod p)\)

欧拉函数

\(\varphi(n)\)，表示小于等于n的正整数中和n互质的数的个数，如\(\varphi(1)=1\)

• 当n是质数时，有\(\varphi(n)=n-1\)

• 欧拉函数是积性函数，即对任意满足\(\gcd(a,b)=1\)的整数a,b，有\(\varphi(ab)=\varphi(a)\varphi(b)\)

  特别地，当n是奇数时\(\varphi(2n)=\varphi(n)\)

求一个数的欧拉函数值：在质因数分解的同时求解即可

1
2
3
4
5
6
7
8
9
10
11

int eular_phi(int n){
    int ans = n;
    for (int i = 2;i*i<=n;i++){
        if (n%i==0){
            ans = ans/i*(i-1);
            while(n%i==0) n/=i;
        } 
    }
    if (n>1) ans = ans/n*(n-1);
    return ans;
}

欧拉定理

若\(\gcd(a,m)=1\)，则\(a^{\varphi(m)}\equiv 1(\bmod m)\)

则对于费马小定理，有更一般的结论：\(x\equiv a^{\varphi(p)-1}(\bmod p)\)

应用

求除法的模运算时，经常会因为精度或溢出问题而导致结果产生误差。

故我们可以将求\(\frac{a}{b}\bmod p\)转化为\(a\cdot b的逆元 \bmod p\)

将除法转为乘法，精度问题便就解决了

扩展欧几里得定理求逆元

给定正整数a，b，求满足\(ax+by=1\)的x的最小正整数解，若无解返回-1

结论

• 当a与b不互质时，逆元必定不存在
• 当a与b互质时，有\(ax+by=ay'+b(x'-\lfloor \frac{a}{b}\rfloor y')\)

对应系数可得： \[ \left\{ \begin{array}{**lr**} x=y' \\ y=x'-\lfloor\frac{a}{b}\rfloor y' \end{array} \right. \] 若改为求满足\(ax\equiv 1(\bmod p)\) 的最小正整数解，经过变形

原式可以由\(ax=kn+1\)变为\(ax+kn=1\)，则和上方一致

模板

1
2
3
4
5
6
7
8

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

费马小定理

给定素数p和正整数a，求满足\(ax\equiv 1(\bmod p)\)的最小正整数x，若不存在返回-1

此时模数固定为素数，故直接可以用费马小定理求解

当a为p的倍数时，\(ax\equiv0(\bmod p)\)，所以一定不存在，返回-1

根据费马小定理有\(a^{p-1}\equiv 1(\bmod p)\)，又\(ax\equiv 1(\bmod p)\)

则\(ax\equiv a^{p-1}(\bmod p)\)，逆元x满足\(x=a^{p-2}(\bmod p)\)

代码

1
2
3
4
5
6
7
8
9
10

int qpow(long long a, int b){
    int ans = 1;
    a = (a%p+p)%p;
    while(b!=0){
        if (b&1) ans = (a*ans)%p;
        a = (a*a)%p;
        b>>=1;
    }
    return ans;
}

线性求逆元

对于求一连串数字模p的逆元，上两种方法容易超时，用这种方法更快一些

结论

(证明见oi-wiki)

有递推式 \[ i^{-1} \equiv \left\{ \begin{array}{**lr**} 1 & i=1\\ -\lfloor\frac{p}{i}\rfloor(p\bmod i)^{-1} & i\neq1 \end{array} \right. \]

代码

1
2
3
4
5
6

void liner(ll n, ll p){
  inv[1]=1;
  for (ll i = 2;i<=n;i++){
    inv[i]=(ll)(p-p/i)*inv[p%i]%p;
  }
}

线性求任意逆元

首先我们求出n个数的前缀积\(s_{i}\)，这时我们可以用exgcd或费马小定理求出\(s_{n}\)的乘法逆元

又因为\((a\times b)^{-1}=a^{-1}\times b^{-1}\)，\(a\times a^{-1}=1\)，故我们可以将\(s_{n}\times a_{n}\)，\(a_{n}\)就会和其逆元抵消，以求出\(s_{inv_{n-1}}\)

求出所有前缀积的逆元后，我们可以让前缀积的逆元乘i-1的前缀积来消除其他逆元，以得到\(a_{i}\)的逆元，即\(s_{i-1}\times sv_{i}=a^{-1}_{i}\)

1
2
3
4
5

s[0]=1;
for (int i = 1;i<=n;i++) s[i]=s[i-1]*a[i]%p;
sv[n]=qpow(s[n],p-2); // 也可以用exgcd
for (int i = n;i>=1;i--) sv[i-1]=sv[i]*a[i]%p;
for (int i = 1;i<=n;i++) inv[i]=sv[i]*s[i-1]%p;