剩余定理模板
C++ 代码
#include <cstdio>
typedef long long ll;
int a[20], m[20], n;
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;
}
ll CRT() {
ll ans = 0;
ll M = 1;
ll t1, t2;
for (int i = 1; i <= n; i++) M *= m[i];
for (int i = 1; i <= n; i++) {
ll Mi = M / m[i];
exgcd(Mi, m[i], t1, t2);
ans = (ans + a[i] * Mi % M * t1) % M;
}
return (ans + M) % M; //保证结果为正整数
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", m + i, a + i);
}
printf("%lld", CRT());
return 0;
}
数据
5
18 9
14 9
10 7
8 5
3 0
会炸
怎么会炸呢
它的答案是5184
那正确答案呢
2277
$M=\prod_{i=1}^n m_i$,为什么不会溢出?
题目数据有问题吧
n比较小,应该可以对每个i便利一遍求出当前的M/mi吧,变成边模好像就不会溢出了
$1.2\times 10^6$的四次就溢出了,没溢出是数据问题。况且这题不能取模。
这题怎么不能取模,x=π mk(k!=i) (mod a[i]),求出x与x的逆元,答案即是Sigma xx(-1)b[i]
? 是我哪里想错了吗