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

Hdu 1573
题意:求同余方程组小于某数的解的个数。

利用中国剩余定理求出最小一个整数解,因为模数不互质,要一一合并。
由于解有周期性,用最大限度值减去最小解除以周期即为答案,但是要记住正整数解不包括0,所以如果最小解为0要舍弃。即如果最小解不在$(0, n]$范围内则整个同余方程组无解。

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
65
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#defin#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 n, m, mi[20], ai[20];
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%lld", &n, &m);
clean();
for (LL i = 1; i <= m; i++) scanf("%lld", &mi[i]);
for (LL i = 1; i <= m; i++) scanf("%lld", &ai[i]);
for (LL i = 2; i <= m; 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) {
return printf("0\n"), 0;
}
a /= g, b /= g, c /= g;
exgcd(a, b, x1, x2);
b = (b > 0) ? b : -b;
x1 = (x1 * c % b + b) % b;
ai[i] = ai[i - 1] + mi[i - 1] * x1;
mi[i] = lcm(mi[i], mi[i - 1]);
}
LL x1, x2, a = 1, b = -mi[m], c = ai[m];
LL g = gcd(a, b);
if (c % g != 0) {
return printf("0\n"), 0;
}
a /= g, b /= g, c /= g;
exgcd(a, b, x1, x2);
b = (b > 0) ? b : -b;
x1 = (x1 * c % b + b) % b;
LL ans = (n - x1) / b;
if (x1 != 0 && x1 <= n) ans++;
printf("%lld\n", ans);
return 0;
}
int main() {
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
------ 本文结束 ------