黑科技？
gcd
辗转相除法
求 $2$ 个数的gcd时间为 $O(\log{\frac{\min(a, b)}{\gcd(a, b)}})$
求 $n$ 个数的gcd时间为 $O(n + \log V)$
高精+取模
- 若 $2 \mid a \wedge 2 \mid b$ ，则 $\gcd(a, b) = 2 \gcd(\frac{a}{2}, \frac{b}{2})$
- 若 $2 \mid a \wedge 2 \not\mid b(2 \not\mid a \wedge 2 \mid b)$ ，则 $\gcd(a, b) = \gcd(\frac{a}{2}, b)$
- 若 $2 \not\mid a \wedge 2 \not\mid b$ ，则 $\gcd(a, b) = \gcd(a - b, b)$
不难发现时间为 $O(\log n)$
正题：预处理法
$O(n)$ 预处理， $O(1)$ 查询小于等于 $n$ 的gcd
引理
对于任意数 $n$ 存在分解 $n = abc$ 满足 $a, b, c$ 要么是质数，要么 $\le \sqrt{n}$
证明：
- 若 $n$ 存在一个 $> \sqrt{n}$ 的质因数，显然成立
- 若 $n$ 的质因数全都 $\le \sqrt{n}$ ，取出 $n$ 的最小质因数 $p$ ：
- 若 $p > \sqrt[4]{n}$ ，显然 $n$ 的其它质因数也 $> \sqrt[4]{n}$ ，那么只要把 $n$ 分解质数即可（ $n$ 决不会有大于 $3$ 个质因数）
- 否则我们求出 $\frac{n}{p}$ 的分解 $a’, b’, c’$ ，设其中最小的是 $a’$ （明显它 $\le \sqrt[3]{\frac{n}{p}}$ ），可得 $a’p \le \sqrt[3]{\frac{n}{p}} p = \sqrt[3]{np^2} \le \sqrt[3]{n \sqrt{n}} = \sqrt{n}$ ，则 $n$ 的分解为 $a’p, b’, c’$
证明同时也给出了分解的求法
预处理
求出 $\le \sqrt{n}$ 的所有数的两两的gcd，具体的， g[a][b] = g[b][a % b] ，可以做到 $O((\sqrt{n})^2) = O(n)$
还要求出所有数的分解，这可以先线性筛，然后用证明的方法求
查询
设求 $x = abc, y$ 的gcd，可以把 $a, b, c$ 和 $y$ 合并，以 $a$ 为例：
- 若 $a > \sqrt{n}$ ，则 $a$ 为质数，去 $2$
- 若 $a$ 为质数，判
y % a 即可
- 否则， $\gcd(y, a) = \gcd(y \mod a, a)$ 直接调用预处理
代码
C Language Practice
然而因为卡空间，这份代码并不能过（要把 fen 的下标改成从 $0$ 开始）
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include <bits/stdc++.h>
#define STC static
using namespace std;
const int N = 2000 + 5, V = 1000000 + 5, W = 1000 + 5;
int g[W][W], fen[V][4];
vector<int> pri;
int num[V];
void prev()
{
for (int i = 0; i < W; ++i)
for (int j = 0; j <= i; ++j)
g[i][j] = g[j][i] = ((i && j) ? g[j][i % j] : (i | j));
num[1] = 1;
for (int i = 2; i < V; ++i)
{
if (!num[i])
pri.push_back(i), num[i] = i;
for (int j : pri)
{
if (j > num[i] || j * i >= V)
break;
num[i * j] = j;
}
}
fen[1][1] = fen[1][2] = fen[1][3] = 1;
for (int i = 1; i < V; ++i)
{
fen[i][1] = fen[i / num[i]][1];
fen[i][2] = fen[i / num[i]][2];
fen[i][3] = fen[i / num[i]][3];
if (fen[i][1] * num[i] < W)
fen[i][1] *= num[i];
else if (fen[i][2] * num[i] < W)
fen[i][2] *= num[i];
else
fen[i][3] *= num[i];
}
}
int _gcd(int x, int y)
{
if (x < W && y < W)
return g[x][y];
else if (!x || !y)
return x | y;
int res = 1;
for (int i = 1, t; i <= 3; ++i)
{
if (fen[x][i] == 1)
continue;
if ((t = fen[x][i]) == num[t])
{
if (y % t == 0)
y /= t, res *= t;
}
else
t = g[t][y % t], y /= t, res *= t;
}
return res;
}
int main()
{
prev();
int T, n, m;
unsigned int ans;
STC int a[N], b[N];
scanf("%d", &T);
while (T--)
{
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= m; ++i)
scanf("%d", &b[i]);
ans = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
ans += _gcd(a[i], b[j]) ^ (i - 1) ^ (j - 1);
printf("%u\n", ans);
}
return 0;
}
|