中国剩余定理模板（互质与非互质）

本文主要是介绍中国剩余定理模板（互质与非互质），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

互质

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{if(b==0){x=1,y=0;return a;}int d=exgcd(b,a%b,y,x);y-=a/b*x;return d;
}
int Chinese_Remainder(int mod[],int prime[],int len)
{int i,d,x,y,m,n,ret;ret=0,n=1;for(int i=0;i<len;i++) n*=prime[i];for(int i=0;i<len;i++){m=n/prime[i];d=exgcd(prime[i],m,x,y);ret=(ret+y*m*mod[i])%n;}return (n+ret%n)%n;
}
int main()
{int n,i;int mod[15],prime[15];while(scanf("%d",&n)&&n){for(int i=0;i<n;i++)scanf("%d%d",&prime[i],&mod[i]);printf("%d\n",Chinese_Remainder(mod,prime,n));}return 0;
}

非互质

#include<bits/stdc++.h>
using namespace std;
#define LL __int64
const LL maxn=20;
void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{if(!b) {d=a;x=1,y=0;}else{   exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}
LL Chinese_Remainder(LL n,LL a[],LL b[])
{LL m1,r1,m2,r2,flag=0,i,d,x,y,c,t;m1=a[0],r1=b[0];flag=0;for(int i=1;i<n;i++){m2=a[i],r2=b[i];if(flag) continue;exgcd(m1,m2,d,x,y);c=r2-r1;if(c%d){flag=1;continue;}t=m2/d;x=(c/d*x%t+t)%t;r1=m1*x+r1;m1=m1*m2/d;}if(flag) return -1;if(n==1&&r1==0) return m1;return r1;
}
int main()
{LL T,i,n,tt=0;LL a[maxn],b[maxn];cin>>T;while(T--){cin>>n;for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<n;i++)cin>>b[i];cout<<"Case "<<++tt<<":"<<Chinese_Remainder(n,a,b)<<endl;}return 0;
}

这篇关于中国剩余定理模板（互质与非互质）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---