49 lines
1.6 KiB
C++
49 lines
1.6 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
#define int long long
|
||
#define endl "\n"
|
||
const int N = 20;
|
||
typedef __int128 INT128;
|
||
|
||
int n; // 同余方程个数
|
||
int a[N]; // 除数数组
|
||
int m[N]; // 余数数组
|
||
int A = 1; // 除数累乘积
|
||
int x, y; // (x,y)是方程 Mi * x + m[i] * y = 1的一个解，x是Mi关于m[i]的逆元
|
||
int res; // 最小整数解
|
||
// 扩展欧几里得模板
|
||
int exgcd(int a, int b, int &x, int &y) {
|
||
if (!b) {
|
||
x = 1, y = 0;
|
||
return a;
|
||
}
|
||
int d = exgcd(b, a % b, y, x);
|
||
y -= a / b * x;
|
||
return d;
|
||
}
|
||
|
||
// 中国剩余定理模板
|
||
void CRT() {
|
||
// 一、预处理
|
||
for (int i = 1; i <= n; i++) {
|
||
cin >> a[i] >> m[i]; // 读入除数数组和余数数组
|
||
m[i] = (m[i] % a[i] + a[i]) % a[i]; // ① 预算余数为正数： r[i]可能为负数，预处理成正数,本题没有这个要求，但考虑到通用模板，加上了这块代码
|
||
A *= a[i]; // ② 预处理除数连乘积
|
||
}
|
||
// 二、计算
|
||
// 功能: 求 x ≡ r_i mod m_i 方程组的解
|
||
for (int i = 1; i <= n; i++) {
|
||
int Ai = A / a[i]; // ①除数连乘积除去当前的除数，得到Mi
|
||
exgcd(Ai, a[i], x, y); // ②扩欧求逆元
|
||
x = (x % a[i] + a[i]) % a[i]; // ③逆元防负数
|
||
res = (res + INT128(m[i] * A / a[i] * x) % A) % A; // ④累加res（看公式） 快速乘,防止LL也在乘法过程中爆炸
|
||
}
|
||
}
|
||
|
||
signed main() {
|
||
cin >> n;
|
||
CRT();
|
||
cout << res << endl;
|
||
}
|