逆元

前置知识

单位元

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

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

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

模乘的单位元是 (证明自己搜)

逆元

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

模意义下的乘法逆元

若 且(a与p互质)，则称a关于模p的乘法逆元为x

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

费马小定理

若p为质数，则，则

或对于任意整数a，有

欧拉函数

，表示小于等于n的正整数中和n互质的数的个数，如

• 当n是质数时，有

• 欧拉函数是积性函数，即对任意满足的整数a,b，有

  特别地，当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;
}

欧拉定理

若，则

则对于费马小定理，有更一般的结论：

应用

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

故我们可以将求转化为

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

扩展欧几里得定理求逆元

给定正整数a，b，求满足的x的最小正整数解，若无解返回-1

结论

• 当a与b不互质时，逆元必定不存在
• 当a与b互质时，有

对应系数可得： 若改为求满足 的最小正整数解，经过变形

原式可以由变为，则和上方一致

模板

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，求满足的最小正整数x，若不存在返回-1

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

当a为p的倍数时，，所以一定不存在，返回-1

根据费马小定理有，又

则，逆元x满足

代码

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)

有递推式

代码

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个数的前缀积，这时我们可以用exgcd或费马小定理求出的乘法逆元

又因为，，故我们可以将，就会和其逆元抵消，以求出

求出所有前缀积的逆元后，我们可以让前缀积的逆元乘i-1的前缀积来消除其他逆元，以得到的逆元，即

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;