0%

[TJOI2009] 猜数字

题目

题目链接

题目大意: 分别给出 $k$ 个数 $\{a_k\}, \{b_k\}$. 求最小的自然数 $n$ 满足 $\forall i \in [1, k], b_i | (n - a_i)$. $1 \le k \le 10, |a_i| \le 10^9, 1 \le b_i \le 6 \times 10^3, \prod b_i \le 10^{18}, b_i$ 两两互质.

思路

由 $b_i | (n - a_i)$ 得到 $n - a_i = xb_i$, 即 $n \equiv a_i \pmod {b_i}$.

由于 $b_i$ 两两互质, 可以用 CRT 求解.

相乘可能会爆 long long, 使用龟速乘来解决这个问题.

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef unsigned long long uLL;
typedef long long LL;

LL a[20], b[20];
LL n, k, ans, M = 1;

LL mul(LL a, LL b, LL mod) {
LL s = 0;
while (b) {
if (b & 1) s = (s + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return s;
}

void exGcd(LL a, LL b, LL &x, LL &y) {
if (!b) {
x = 1, y = 0;
return ;
}
exGcd(b, a % b, y, x);
y -= a / b * x;
}

LL inv(LL a, LL b) {
LL x, y;
exGcd(a, b, x, y);
return x;
}

int main() {
read(k);
for (int i = 1; i <= k; ++i) read(a[i]);
for (int i = 1; i <= k; ++i) read(b[i]), M *= b[i];
for (int i = 1; i <= k; ++i) {
LL mi = M / b[i], ti = inv(mi, b[i]);
ans = ((ans + mul(ti * a[i], mi, M)) % M + M) % M;
}
printf("%lld\n", ans);
return 0;
}