中国剩余定理 C++

题目

解题思路

原链接：https://www.acwing.com/solution/content/3539/

大致步骤：

1. 将第2,3,4…n个方程不断与第一个方程合并，得到方程a1k1+a2k2=m2-m1;
2. 用扩展欧几里得算法解出a1k1+a2k2=gcd(a1, a2)的结果，再将结果扩大(m2-m1)/d倍即可得到原方程解；
3. k1通解=k1+a2/dk(k为整数),将k1代回x=a1k1+m1中，可得x=a1k1+a1a2/d*k+m1;
4. 对比代回前后两方程可得：m1=m1+a1k1, a1=a1a2/d;
5. 循环n-1次后所得m1就是结果;

代码实现

#include<iostream>
#include<algorithm>
#include<cmath>using namespace std;typedef long long LL;LL m1, a1;
LL a[50], m[50];
int n;LL exgcd(LL a, LL b, LL &x, LL &y)
{if(b == 0){x = 1, y = 0;return a;}LL x1, y1, t;t = exgcd(b, a % b, x1, y1);x = y1, y = x1 - a / b * y1;return t;
}void chinese_reminder_therome(LL a1, LL m1)
{for(int i = 2;i <= n;i ++ ){LL a2 = a[i];LL m2 = m[i];LL k1, k2;LL d = exgcd(a1, a2, k1, k2);if((m2 - m1) % d != 0)//只有(m2-m1)%d==0，才有整数解；{cout << -1;return ;}LL t = abs(a2 / d);k1 = k1 * (m2 - m1) / d;k1 = (k1 % t + t) % t;//找到k1的最小值，同时防止为k1为负数的写法m1 = m1 + a1 * k1;//先变m1再变a1，顺序不能变防止m1的变化受到a1的变化影响；a1 = a1 * a2 / d;}cout << m1;
}int main()
{cin >> n >> a1 >> m1;for(int i = 2;i <= n;i ++ ){scanf("%d%d", &a[i], &m[i]);}chinese_reminder_therome(a1, m1);return 0;
}