中国剩余定理预备知识：扩展欧几里得
扩展欧几里得：
用来计算最小公倍数，及其求解线性方程和同余方程
中国剩余定理：
首先假如我们求出这样三个数
k1,k2,k3
k1,k2,k3
，满足k1模3余1且是5和7的倍数，k2模5余1且是3,7的倍数，k3模7余1且是3和5的倍数，那么容易意会得到，
k1∗2+k2∗3+k3∗2
k1∗2+k2∗3+k3∗2
一定会是一个满足题目条件的数。而题目的通解可表示为这个数每次都加上3,5,7的最小公倍数
首先我们求出3，5，7的lcm=105
然后我们令：
x1=105/3=35
x1=105/3=35
,
x2=105/5=21
x2=105/5=21
,
x3=105/7=15
x3=105/7=15 然后我们求解以下方程：
a∗x1%3=1
a∗x1%3=1
,
b∗x2%5=1
b∗x2%5=1
,
c∗x3%7=1
c∗x3%7=1 啊呀这个格式的式子好眼熟。。。那么就愉快地用扩展欧几里德求出来吧！
a=2,b=1,c=1。
答案就是：
ans=(a∗x1∗2+b∗x2∗3+c∗x3∗2)%lcm=23 注意：这是我从博客中写的，不一定编译通过，但是思路不会有问题，代码有瑕疵。(请不要复制粘贴） #include #include #include #include #include #include using namespace std; int n; int m[105]; int p[105]; int exgcd(int a,int b,int &x,int &y){//扩展欧几里得 if(!b){ x = 1; y = 0; return a; } int re = exgcd(b,a%b,x,y); int tmp = x; x = y; y = tmp-(a/b)*y; return re; } int china(){ int sum = 0; int lcm = 1; int x,y; for(int i=1;i<=n;i++){ lcm = (lcm*m[i]); } for(int i=1;i<=n;i++){ int tp = lcm/m[i]; int d = exgcd(tp,m[i],x,y); x = (x%m[i]+m[i])%m[i]; sum = (sum+tp*p[i]*x)%lcm; } return (sum+lcm)%lcm; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&p[i]); } for(int i=1;i<=n;i++){ scanf("%d",&m[i]); } printf("%d ",china()); }