逆元

Tang7O

ACM算法

发布于：2020年4月10日

次浏览

字数统计: 528字   |   阅读时长: 2分

由于C++储存数据的范围是有限的，当数据超出储存范围时计算就会出错，为了避免错误，一般使用求余的方法。 $(a+b)\%c$可以表示为$(a\%c+b\%c)\%c$，乘法同理

减法也可以表示为$(a+c-b)\%c$

但是除法怎么办呢？

想一下除法计算过程：$a/b=a* 1/b$

那么自然会想到，把$(a/b)\%c$变成$(a(1/b))$不就可以了吗。
但是现实是残酷的，取余是建立在除数和被除数都算整数的基础上的，浮点数无法进行取余计算。那么我们可不可以在$1～c-1$中找到一个数x使得$(a/b)\%c==(ax)\%c$ 呢？即$b x=1(\%c)$;
答案是肯定的！
这个x就叫做b的逆元，或者叫做数论倒数(和正常意义上的倒数不一样，但和正常意义上的倒数具有相同的作用)。
有逆元的充要条件
$a$在mod c意义下有逆元的充要条件：GCD(a,c)=1
那么*逆元要怎么求呢？

1. EXGCD
   求a在mod c意义下的逆元，可以转化为求 ax+cy=1 ；
   就可以用EXGCD求逆元了。

1
2
3
4
5

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

1. 费马小定理
   如果p为质数，则$a^{p−1}≡1\%p$
   $∴a*a^{p−2}≡1\%p$
   快速幂求$a^{p-2}$就可以啦。

1
2
3
4
5
6
7
8
9
10
11

int q_pow(int a,int n,int m) {    
    int ans = 1;    
    while(n) {    
        if (n&1) {    
            ans = ans*a%m;    
        }     
        a = a*a%m;   
        n >>= 1;    
    }    
    return ans;    
}   

1. 欧拉定理
   将费马小定理中的p−2换为φ( p )−1即可
   p可以不是质数
2. 递推
   用于O(n)预处理[1⋯n]的逆元
   构造$p=k i+r$
   $∴k i+r≡0\%p $
   $∴k i=−r $
   $∴i−1=−k r−1 $
   其中$k=⌊pi⌋,r=p\%i $
   $∴i−1=−⌊pi⌋⋅inv[p\%i] $
3. 为了防止出现负数，通常的写法是这样的

1

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

参考博客：

https://blog.csdn.net/Gh0stCai/article/details/79968462 https://blog.csdn.net/Adusts/article/details/80627966

更新于：2022年4月13日

算法

知识