表达整数的奇怪方式
给定 2n 个整数a1,a2,…,an和m1,m2,…,mn,求一个最小的非负整数 x,满足∀i∈[1,n],x≡mi(mod ai)。
输入格式
第1 行包含整数 n。
第 2..n+1行:每 i+1 行包含两个整数ai和mi,数之间用空格隔开。
输出格式
输出最小非负整数 x,如果 x 不存在,则输出 −1。
如果存在 x,则数据保证 x 一定在64位整数范围内。
数据范围
1≤ai≤231−1,
0≤mi<ai
1≤n≤25
输入样例:
2
8 7
11 9
输出样例:
31
由于ACWing 的公式编辑器无法编辑方程组,此处补充一个链接,描述拓展CRT的全部推导
https://blog.csdn.net/qq_38228254/article/details/113485263
C++ 代码
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
/*
拓展欧几里得算法计算逆元;
*/
LL exgcd(LL a, LL b, LL &x, LL &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
// 计算取模条件下的最小值, 其中 a = k*b + c;
LL inline mod(LL a, LL b) {
return ((a % b) + b) % b;
}
int main() {
int n;
cin >> n;
LL a1, m1;
cin >> a1 >> m1;
// 输入剩余的 n-1 个方程
for (int i = 0; i < n - 1; i++) {
LL a2, m2;
scanf("%lld%lld", &a2, &m2);
// 对第一个方程进行分析
// 为 a1的系数k1 计算特解,继而计算通项,以便后续合并
LL k1, k2;
LL gcd = exgcd(a1, a2, k1, k2);
// 无解情况 联立前两个方程得到方程组可得
if ((m2 - m1) % gcd) {
printf("-1\n");
return 0;
}
/* 从数学推导可以得到 k1特解:k1' = k1 * (m2 - m1)/gcd (由欧几里得算法得到)
k1 = k1' + k * a2/gcd
出于稳妥,维护k1 的最小值
*/
k1 = mod(k1 * (m2 - m1) / gcd, abs(a2 / gcd));
// 表示合并后方程的 x = k' * a1 + m1 中m1 和 a1 的值;
// 更新后进入循环继续合并
m1 = k1 * a1 + m1;
a1 = abs(a1 / gcd * a2);
}
// x = k' * a1 + m1,计算符合条件的最小x
printf("%lld\n", (m1 + a1)%a1);
return 0;
}