【题目来源】
洛谷：P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 - 洛谷 (luogu.com.cn)
【题目描述】
自从曹冲搞定了大象以后，曹操就开始捉摸让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲满不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。举个例子，假如有 \(16\) 头母猪，如果建了 \(3\) 个猪圈，剩下 \(1\) 头猪就没有地方安家了。如果建造了 \(5\) 个猪圈，但是仍然有 \(1\) 头猪没有地方去，然后如果建造了 \(7\) 个猪圈，还有 \(2\) 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？
【输入】
第一行包含一个整数 \(n\) —— 建立猪圈的次数，接下来 \(n\) 行，每行两个整数 \(a_i,b_i\)，表示建立了 \(a_i\) 个猪圈，有 \(b_i\) 头猪没有去处。你可以假定 \(a_1\sim a_n\) 互质。
【输出】
输出包含一个正整数，即为曹冲至少养母猪的数目。
【输入样例】
3
3 1
5 1
7 2
【输出样例】
16
【算法标签】
《洛谷 P1495 中国剩余定理（CRT）》 #数学# #中国剩余定理CRT#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 将int定义为long long类型
const int N = 15; // 最大方程数量
int n; // 同余方程组数量
int m[N], r[N]; // m: 模数数组，r: 余数数组// 扩展欧几里得算法，返回gcd(a,b)，并计算ax+by=gcd(a,b)的一组解
int exgcd(int a, int b, int &x, int &y)
{if (!b) // 递归终止条件{x = 1; // 当b=0时，x=1y = 0; // 当b=0时，y=0return a; // 返回最大公约数}int x1, y1, d;d = exgcd(b, a % b, x1, y1); // 递归计算x = y1; // 更新xy = x1 - a / b * y1; // 更新yreturn d; // 返回最大公约数
}// 中国剩余定理（Chinese Remainder Theorem）求解同余方程组
int CRT(int m[], int r[])
{int M = 1, ans = 0; // M: 所有模数的乘积for (int i = 1; i <= n; i++) // 计算M{M *= m[i];}for (int i = 1; i <= n; i++){int c = M / m[i]; // Mi = M/miint x, y;exgcd(c, m[i], x, y); // 求解 Mi*x ≡ 1 (mod mi)ans = (ans + r[i] * c * x % M) % M; // 累加 ai*Mi*xi}return (ans % M + M) % M; // 确保结果为非负最小整数解
}signed main() // 因为定义了int为long long，所以使用signed main
{cin >> n; // 读入方程数量for (int i = 1; i <= n; i++){cin >> m[i] >> r[i]; // 读入每个方程的模数和余数}cout << CRT(m, r) << endl; // 输出同余方程组的解return 0;
}
// 调整int的范围，保证最后一个样例通过
#include <bits/stdc++.h>
using namespace std;// #define ll long long
typedef long long ll; // 定义ll为long long类型
#define ll __int128 // 实际上将ll重新定义为__int128类型
const int N = 15; // 最大方程数量
int n; // 同余方程组数量
int m[N], r[N]; // m: 模数数组，r: 余数数组// 扩展欧几里得算法，使用__int128类型
ll exgcd(ll a, ll b, ll &x, ll &y)
{if (!b) // 递归终止条件{x = 1; // 当b=0时，x=1y = 0; // 当b=0时，y=0return a; // 返回最大公约数}ll x1, y1, d;d = exgcd(b, a % b, x1, y1); // 递归计算x = y1; // 更新xy = x1 - a / b * y1; // 更新yreturn d; // 返回最大公约数
}// 中国剩余定理（Chinese Remainder Theorem）求解同余方程组
ll CRT(int m[], int r[])
{ll M = 1, ans = 0; // M: 所有模数的乘积for (int i = 1; i <= n; i++) // 计算M{M *= m[i];}for (int i = 1; i <= n; i++){ll c = M / m[i]; // Mi = M/mill x, y;exgcd(c, m[i], x, y); // 求解 Mi*x ≡ 1 (mod mi)ans = (ans + r[i] * c * x % M) % M; // 累加 ai*Mi*xi}return (ans % M + M) % M; // 确保结果为非负最小整数解
}int main()
{scanf("%lld", &n); // 读入方程数量for (ll i = 1; i <= n; i++){scanf("%lld%lld", m + i, r + i); // 读入每个方程的模数和余数}printf("%lld\n", CRT(m, r)); // 输出同余方程组的解return 0;
}
【运行结果】
3
3 1
5 1
7 2
16