【题目来源】
AcWing：204. 表达整数的奇怪方式 - AcWing题库
【题目描述】
给定 \(2n\) 个整数 \(a_1,a_2,\dots,a_n\) 和 \(m_1,m_2,\dots,m_n\)，求一个最小的非负整数 \(x\)，满足 \(\forall \in [1,n],x\equiv m_i(mod\ a_i)\)。
【输入】
第 \(1\) 行包含整数 \(n\)。
第 \(2\dots n+1\) 行：每 \(i+1\) 行包含两个整数 \(a_i\) 和 \(m_i\)，数之间用空格隔开。
【输出】
输出最小非负整数 ，如果 \(x\) 不存在，则输出 \(-1\)。
【输入样例】
2
8 7
11 9
【输出样例】
31
【解题思路】
【算法标签】
《AcWing 204 表达整数的奇怪方式》 #数学知识# #同余方程# #扩展中国剩余定理#
【代码详解】
#include <bits/stdc++.h>
using namespace std;typedef long long LL; // 定义 LL 为 long long 类型// 扩展欧几里得算法，用于求解 ax + by = gcd(a, b) 的一组整数解
LL exgcd(LL a, LL b, LL &x, LL &y)
{if (b == 0) { // 如果 b 为 0，递归终止x = 1, y = 0; // 解为 x = 1, y = 0return a; // 返回 gcd(a, b)}LL r = exgcd(b, a % b, x, y); // 递归求解LL x1 = x, y1 = y; // 保存递归结果x = y1, y = x1 - a / b * y1; // 更新 x 和 yreturn r; // 返回 gcd(a, b)
}int main()
{int n; // 定义整数 n，表示方程的数量bool has_answer = true; // 标记是否有解LL a1, m1; // a1 和 m1 表示第一个方程的系数和常数项cin >> n; // 输入方程的数量cin >> a1 >> m1; // 输入第一个方程的系数和常数项// 循环处理剩余的 n - 1 个方程for (int i = 0; i < n - 1; i++) {LL a2, m2; // a2 和 m2 表示下一个方程的系数和常数项cin >> a2 >> m2; // 输入下一个方程的系数和常数项LL k1, k2; // k1 和 k2 用于存储扩展欧几里得算法的解// 使用扩展欧几里得算法求解 a1 * k1 + a2 * k2 = gcd(a1, a2)LL d = exgcd(a1, a2, k1, k2);// 如果 (m1 - m2) 不能被 gcd(a1, a2) 整除，则无解if ((m1 - m2) % d) {has_answer = false; // 标记无解break; // 跳出循环}// 调整 k1 和 k2 的值k1 = k1 * (m2 - m1) / d;k2 = k2 * (m2 - m1) / d;LL t = a2 / d;// 保证 k1 为最小非负整数解k1 = (k1 + t) % t;// 更新 m1 的值m1 = a1 * k1 + m1;// 更新 a1 的值a1 = a1 / d * a2;}if (has_answer) // 输出最小非负整数解cout << (m1 + a1) % a1 << endl;else // 无解输出 -1cout << -1 << endl;return 0; // 程序结束
}
【运行结果】
2
8 7
11 9
31