Hdu 3579(扩展中国剩余定理)

poj 3579

模数不互质的中国剩余定理模板,证明见

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
LL kase, n, mi[10], ai[10];
LL gcd(LL a, LL b) {
if (b == 0) return a;
return gcd(b, a % b);
}
LL lcm(LL a, LL b) {
return a * b / gcd(a, b);
}
void exgcd(LL a, LL b, LL &x, LL &y) {
if (b == 0) {
x = 1, y = 0;
return ;
}
exgcd(b, a % b, x, y);
LL tmp = x;
x = y, y = tmp - (a / b) * y;
}
void clean() {}
int solve() {
scanf("%lld", &n);
clean();
LL fl = false;
for (LL i = 1; i <= n; i++) scanf("%lld", &mi[i]);
for (LL i = 1; i <= n; i++) scanf("%lld", &ai[i]);
LL ll = mi[1];//所有的lcm
for (LL i = 2; i <= n; i++) {//合并n-1次
ll = lcm(ll, mi[i]);
LL x1, x2, a = mi[i - 1], b = mi[i], c = ai[i] - ai[i - 1];
LL g = gcd(a, b);
if (c % g != 0) {fl = true; break;}
a /= g, b /= g, c /= g;
exgcd(a, b, x1, x2);
b = (b > 0) ? b : -b;
x1 = (x1 * c % b + b) % b;
mi[i] = lcm(mi[i], mi[i - 1]);
ai[i] = ai[i - 1] + mi[i - 1] * x1;
}
if (fl) printf("Case %lld: -1\n", kase); else {//计算最后一个
LL x1, x2, a = 1, b = -mi[n], c = ai[n];
LL g = gcd(a, b);
a /= g, b /= g, c /= g;
exgcd(a, b, x1, x2);
b = (b > 0) ? b : -b;
x1 = (x1 * c % b + b) % b;
if (x1 == 0) {
printf("Case %lld: %lld\n", kase, ll);
} else printf("Case %lld: %lld\n", kase, x1);
}
return 0;
}
int main() {
kase = 0;
LL T; scanf("%lld", &T);
while (T--) kase++, solve();
return 0;
}
------ 本文结束 ------