模运算
强烈推荐先看这个视频:哔哩哔哩——模意义下的乘法逆元
csdn_扩展欧几里得算法
同余关系:
$$ a≡b\ (mod \ n) $$
上式记为a与b在对n取余时相等。
比如3≡8(mod 5) 4≡6(mod 2)
下面介绍四种运算下的模运算:+、-、*、/
加法下的模运算
15%4=3
9%4=1
(15+9)%4=0
有
$$
(a+b)\ mod\ n=(a\ mod\ n+ b\ mod\ n)\ mod \ n
$$
乘法下的模运算
与加法类似
3%4=3 5%4=1
(3 * 5) % 4=15 % 4 = 3
有
$$
(a\times b)\ mod\ n=(a\ mod\ n\times b\ mod\ n)\ mod \ n
$$
减法下的模运算—⚠️
减法取模运算同样与加法乘法类似,但是有一点需要注意的是,由于在进行减法运算后结果可能是负数,因此需要加上一个n后再取模。
$$
(a-b)\ mod\ n=(a\ mod\ n-b\ mod\ n+n)\ mod\ n
$$
除法下的模运算
除法就麻烦一些了 比如
$$
\frac{3}{7}\%4
$$
就完全不能用上面的公式了
我们就要找到一个 7的倒数x(在模4的情况下)即
$$
7\times x≡1(\ mod\ 4)(这个x就相当于普通运算下的\frac{1}{7})
$$
这个x乘上7再%4的结果为1
这样我们这样做就行了:
$$
[\frac{3}{7} \times (7\times x)\ ]\%\ 4
$$
因为7*x与1在模4的情况下同余嘛,所以乘上一个7 * x不会影响结果
就转化成了
$$
(3\times x)\%4
$$
这个x,我们把它叫做 7在模4运算下的乘法逆元,记作x = lnv( 7 )。
mod=8时,lnv(3)=3(因为3*3%8=1)
lnv( )并不是任何时候都有解,比如当mod=8,lnv(4)便无解。
定理:只有 mod 与 x 互质时,lnv( x )才有解。
补充
为什么一般题目都要求对998244353或者1e+7取余呢?(mod=998244353 or 1e+7)
因为998244353和1e+7都是质数,意味着1~998244353-1或者1~1e+6的所有数都与这两个mod互质。
所以当要做除法的模运算时,只要被除数在1~998244353-1,就都可以找到其乘法逆元,而不存在无解的情况。
求x的乘法逆元x^-1(在对M取余时)
$$ x\times x^{-1}≡1(\%M) $$
朴素做法
根据乘法的公式:
$$
(a\times b)\ mod\ M=(a\ mod\ n\times b\ mod\ M)\ mod \ M
$$
x^-1 mod M肯定属于1~M-1
我们令x^-1=x^-1 mod M,依次遍历1~M-1
for(int i=1;i<=M-1;i++){
if(x*i%M==1) return i;
}
时间复杂度:O(M)
费马小定理做法
费马小定理:
$$
当M为质数时:x^{M-1}≡1(mod\ M)
$$
推导一下:
$$
当M为质数时:x\times x^{M-2}≡1(mod\ M)
$$
$$ 又因为\ x\times x^{-1}≡1(mod\ M) $$
$$ x^{-1}=x^{M-2} $$
即lnv( x )=x的M-2次方。
求x的M-2次方可以用快速幂来做。
证明
设两个序列:
$$
p:1、2、…、M-1
$$
$$ q:a、2a、…、(M-1)\times a $$
在对M取余的情况下,q序列实际上就是打乱的p序列,即set(p)==set(q),里面元素完全一样,只是顺序不同。
$$
p_i≡q_j(mod\ M)
$$
比如,a=5,M=7时
这里证明参考循环群。
$$
p序列元素相乘=(M-1)!,q序列元素相乘=(M-1)!\times a^{M-1}
$$
因为
$$
p_i≡q_j(mod\ M)
$$
所以
$$
(M-1)!\%M≡(M-1)!\times a^{M-1}\%M(mod\ M)
$$
因为M是质数,所以(M-1)!肯定存在 乘法逆元,两边同时乘以它:
$$
1≡a^{M-1}\ (mod\ M)
$$
证明完毕。
具体到这道题
这个题保证给的M都是质数,首先M与比M小的正整数都互质。
我们只需要保证x不是M的倍数即可,就能保证x与M互质,就能保证lnv(x)有解。
$$
M是质数时,if\ x≠M的倍数\ ,x与M互质,lnv(x)有解
$$
代码
#include<iostream>
using namespace std;
#include<algorithm>
typedef long intt;
intt result[30];
intt lnv(intt x,intt M){
intt b=M-2;
result[0]=x;
for(intt inspect=2,i=1;inspect<=b;i++,inspect=inspect<<1){
result[i]=(result[i-1]*result[i-1])%M;
}
intt temp,j=0,product=1;
while(temp=(b>>j)){
if(temp&1){
product=product*result[j]%M;
}
j++;
}
return product;
}
int main(void){
intt n,x,M;
cin>>n;
for(intt i=1;i<=n;i++){
cin>>x>>M;
if(x%M!=0){
cout<<lnv(x,M)<<endl;
}else{
cout<<"impossible"<<endl;
}
}
}
扩展欧几里得算法求乘法逆元的做法
$$ 裴蜀定理:对于任何正整数a,b,一定存在非零整数x,y,使得a\times x+b\times y=gcd(a,b)。 $$
解释:a是gcd(a,b)的倍数,b也是gcd(a,b)的倍数,那么ax+by一定是gcd(a,b)的倍数。
补充:对于任何自然数a,有\ gcd(a,0)=gcd(0,a)=|a|
扩展欧几里得算法就可以求出x和y来,那么与求a在模b的意义下的乘法逆元何干呢?
$$
a\times x+b\times y=gcd(a,b)->a\times x+b\times y≡gcd(a,b)(mod\ b)
$$
通过这个等式可以推导出在模b的意义下等式两边还是相等的,又因为我们求逆元要保证b和a是互质的,那么
$$
gcd(a,b)=1
$$
$$ b\times y≡0(mod\ b) $$
$$ a\times x+b\times y≡gcd(a,b)(mod\ b)->a\times x≡1(mod\ b) $$
我们此时能看出来,x
即为a在模b下的乘法逆元。
相比费马小定理的优点:M不需要是质数。
扩展欧几里得算法
$$ 由裴蜀定理可知,ax_1+by_1=gcd(a,b),bx_2+(a\%b)y_2=gcd(b,a\%b), $$
$$ 由 欧几里得算法(辗转相除法)可知,gcd(a,b)==gcd(b,a\%b) $$
$$ 所以\ ax_1+by_1=bx_2+(a-[\frac{a}{b}]b)y_2=ay_2+b(x_2-[\frac{a}{b}]y_2) $$
$$ 由恒等定理可知 x_1=y_2,y_1=x_2-[\frac{a}{b}]y_2 $$
至此我们得到了关于x、y的递推式:
$$
x_i=y_{i+1},y_i=x_{i+1}-[\frac{a}{b}]y_{i+1}
$$
根据欧几里得算法我们知道,最后的时候有
$$
gcd(a_{n},0)
$$
根据裴蜀定理:
$$
a_{n}x_n+b_ny_n=gcd(a_{n},0)=a_n
$$
$$ a_nx_n+b_ny_n=a_n–>y_n=0,x_n=1 $$
所以我们得到了递归尽头的x和y:$x_n=1,y_n=0$
便可以根据之前得到的递推式算出$x_1$ 和 $y_1$
代码
#include<iostream>
using namespace std;
#include<algorithm>
typedef pair<int,int> II;
II exgcd(int a,int b){//返回{x,y}
if(b==0) return make_pair(1,0);//如果这是最后的递归,x=1,y=0
else{
II temp=exgcd(b,a%b);//先得到下一层的x,y
return make_pair(temp.second,temp.first-a/b*temp.second);//由递归式子得出这一层的x,y
}
}
int main(void){
int n,a,b;
cin>>n;
while(n--){
cin>>a>>b;
II temp=exgcd(a,b);
cout<<temp.first<<" "<<temp.second<<endl;
}
}
第三种方法———线性求逆元
给出n和M(n<=M),求1~n在%M下的乘法逆元。
记住inv[i]=(M-M/i)*inv[M%i]%M;
#include<iostream>
using namespace std;
#include<algorithm>
typedef long intt;
const intt N=100010;
intt inv[N];//inv[i]表示i在%M下的乘法逆元
void niyuan(int n,int M){
inv[1]=1;
for(int i=2;i<=n;i++){
inv[i]=(M-M/i)*inv[M%i]%M;
}
}
int main(void){
intt n,M;
cin>>n>>M;
niyuan(n,M);
for(int i=1;i<=n;i++){
cout<<inv[i]<<endl;
}
}