同余小结
LazySheep
·
·
个人记录
基本运算性质
(a+b)\ mod\ p=(\ (a\ mod\ p)+(b\ mod\ p)\ )\ mod\ p
(a\times b)\ mod\ p=(\ (a\ mod\ p)\times(b\ mod\ p)\ )\ mod\ p
模线性方程
EX_GCD
求方程 ax+by=m 的整数解 x,y。其中 a,b,m 均为给定的整数。
1.
贝祖等式：ax+by=gcd(a,b) 一定存在整数解。
证明：
当 b=0 时，a=gcd(a,b)。所以 1\times a+0\times b=gcd(a,b)。x=1,y=0 是方程的一组解。
根据欧几里得算法，
gcd(a,b)=gcd(b,a\ mod\ b)
=b\times x_0+(a\ mod\ b)\times y_0
=b\times x_0+(a-b\times\left\lfloor\frac{a}{b}\right\rfloor)\times y_0
=b\times x_0+a\times y_0-b\times\left\lfloor\frac{a}{b}\right\rfloor\times y_0
=a\times y_0+b\times(x_0-\left\lfloor\frac{a}{b}\right\rfloor\times y_0)
=a\times x+b\times y
inline int exgcd(int a,int b,int&x,int&y){
if(!b){x=1;y=0;return a;}
int gcd=exgcd(b,a%b,x,y);
int z=x;x=y;y=z-a/b*y;
return gcd;
}
2.
方程有解当且仅当 gcd(a,b)|m。
所以可以先求出 ax+by=gcd(a,b) 的解，再令 x=x\times \frac{m}{gcd(a,b)}，y=y\times \frac{m}{gcd(a,b)} 即可。
注意求解之前这一步一定不能漏判是否有 gcd(a,b)|m。
int gcd=exgcd(a,b,x,y);
if(m%gcd)puts("No solution");
x*=m/gcd;y*=m/gcd;
printf("%d %d",x,y);
3.
设 k\in Z，ax+by=gcd(a,b)，则方程的通解 xx,yy 可表示为
xx=\frac{m}{gcd}x+k\frac{b}{gcd},yy=\frac{m}{gcd}y-k\frac{a}{gcd}
4.
求该方程的非负整数解。
如果最开始求出的特解都 \ge 0，则这两个特解可直接作为答案。
如果两个特解都 \le 0，该方程无非负整数解。
否则，设大于 0 的数为 x，则 $k_{max}=\left\lfloor\frac{x\times\frac{m}{gcd}}{\frac{b}{gcd}}\right\rfloor
将 $k$ 代入 $yy$ 的通解形式后检验即可。
强调：在求非负整数解之前，一定要**判断 $gcd(a,b)|m$ 是否满足**。不满足则无解。
5.
求逆元。
$a$ 在模 $b$ 意义下的逆元 $x$ 满足 $ax\equiv 1(mod\ b)$。
这可推成方程的一个特殊形式：
$$
ax\equiv 1(mod\ b)\Rightarrow gcd(a,b)=1 \Leftrightarrow ax+by=1
$$
那么要求的就是该方程的最小非负整数解。
```cpp
inline int exgcd(int a,int b,int&x,int&y){
if(!b){x=1;y=0;return a;}
int gcd=exgcd(b,a%b,x,y);
int z=x;x=y;y=z-a/b*y;
return gcd;
}
int main(){
exgcd(a,b,x,y);
while(x<0)x+=b;
return 0;
}
```
---
### $O(n)$ 求逆元
预处理前缀积。
```cpp
const int mod=1e9+7,N=5e6+5;
int F[N],G[N],a[N];int n;
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int ksm(int x,int y){
int res=1;
for(;y;y>>=1,x=mul(x,x))
if(y&1)res=mul(res,x);
return res;
}
int main(){
read(n);F[0]=1;
for(int i=1;i<=n;++i){
read(a[i]);
F[i]=mul(F[i-1],a[i]);
}
G[n]=ksm(F[n],mod-2);
for(int i=n-1;i;--i)
G[i]=mul(G[i+1],a[i+1]);
for(int i=1;i<=n;++i)
printf("%d ",mul(F[i-1],G[i]));
return 0;
}
```
常用来预处理阶乘
```cpp
const int mod=1e9+7,N=1e5+5;
int F[N],G[N];
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int ksm(int x,int y){
int res=1;
for(;y;y>>=1,x=mul(x,x))
if(y&1)res=mul(res,x);
return res;
}
int main(){
F[0]=G[0]=1;
for(int i=1;i<N;++i)F[i]=mul(F[i-1],i);
G[N-1]=ksm(F[N-1],mod-2);
for(int i=N-2;i;--i)G[i]=mul(G[i+1],i+1);
return 0;
}
```