这是中国剩余定理的板子题。
为什么用快速幂求逆元会WA?
因为快速幂求逆元是根据费马小定理,其前提是a和m互质且m要是质数。本题a和m互质但是m一定不是质数所以只能用裴蜀定理求。
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int MOD = 100003;
typedef pair<int, int> PII;
const int N = 15;
int n;
int a[N], m[N];
LL M = 1;
LL exgcd(LL a, LL b, LL & x, LL & y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
LL x1, y1;
LL d = exgcd(b, a%b, x1, y1);
x = y1;
y = x1 - a/b*y1;
return d;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin >> n;
for (int i = 0; i < n; i++) {
cin >> m[i] >> a[i];
M *= m[i];
}
LL res = 0;
for (int i = 0; i < n; i++) {
LL Mi = M / m[i];
LL x, y;
exgcd(Mi, m[i], x, y);
res += Mi * a[i] * x;
}
cout << (M + res % M) % M << endl;
return 0;
}