中国剩余定理-模数之间两两互质
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
//中国剩余定理 CRT
int a[200000];
int r[200000];
int x,y;
void exgcd(int a,int b){
if(b==0){
x = 1;
y = 0;
return;
}
exgcd(b,a%b);
int tmp = x;
x = y;
y = tmp - a/b*y;
return;
}
signed main(){
int k;
cin>>k;
int m = 1;
for(int i = 1;i<=k;i++) cin>>a[i]>>r[i],m*=a[i];
int ans = 0;
for(int i = 1;i<=k;i++){
if(a[i]==0){
cout<<r[i];
exit(0);
}
int tmp = m/a[i];
exgcd(tmp,a[i]);
ans = (ans + r[i]*x*tmp%m)%m;
}
cout<<(ans%m+m)%m;
}
拓展中国剩余定理-不保证模数之间两两互质,即逆元法不可用
数学证明见:https://www.luogu.com.cn/blog/blue/kuo-zhan-zhong-guo-sheng-yu-ding-li
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,mod[100009],yu[100009];
//要用快速乘(龟速乘),防止爆long long
ll qMul(ll a,ll b,ll mo){
ll an = 0;
while(b) {
if(b&1) an =(an+a) % mo;
a = (a+a)%mo;
b>>=1;
}return an%mo;
}
//扩展欧几里得算法,返回gcd(a,b),并计算出ax+by = gcd(a,b)中的x和y
ll exGcd(ll a,ll b,ll &x,ll &y){
if( b == 0 ) { x = 1;y = 0; return a;}
ll gcd = exGcd(b,a%b,y,x); //注意x和y的顺序
y = y - a/b*x;
return gcd;
}
int main() {
ios::sync_with_stdio(false);//加速cin和cout
cin>>n;
for(int i = 1;i <= n;i++) cin>>mod[i]>>yu[i];
ll ans = yu[1],M = mod[1] ,t,y; //ans表示前i-1个方程式的特解(余数),M为前i-1个方程式的模数的最小公倍数(i从2开始)
for(int i = 2;i <= n;i++){
ll mi = mod[i],res = ((yu[i] - ans)%mi + mi)%mi; //res是等式的右边部分,不能出现负数
ll gcd = exGcd(M,mi,t,y); //求出gcd(mi,M)
if(res % gcd != 0) { cout<<-1<<endl;exit(0); } //如果等式右边不能整除gcd,方程组无解
t = qMul(t,res/gcd,mi); //求出t还要乘上倍数,注意是快速乘取模mi (对谁取模要分清)
ans += t * M; //得到前i个方程的特解(余数)
M = mi /gcd * M; //M等于lcm(M,mi),注意乘法要在除法后面做,否则会爆long long
ans = (ans%M+M)%M; //让特解范围限定在0~(M-1)内,防止会出现负数
}
cout<<ans;
return 0;
}