题解 洛谷P5435 [模板]快速GCD

发表于 | 分类于 | 阅读次数：

题面

感谢@Duan2baka 指出一处错误

这道题很多人可能会以为要求的东西是有性质
然而确实有预处理$O($值域$)$预处理 $O(1)$查询的方法

首先用线性筛预处理，可以把大多数的数分解成三个不大于$O(\sqrt n)$的数的乘积
如果分解出来大于$O(\sqrt n)$的话，一定是一个质数
具体方法:
1.找出一个数$x$的最小质因子$p$,并得到$\frac xp$的分解
2.把$p$乘到最小的数上即可

证明一下为什么是对的
考虑归纳法
只需证明把$p$乘上最小的数后得到的结果一定不大于$\sqrt n$
$\frac np$分解中最小的一个数$a$一定不大于$\sqrt[3]\frac np$
$a\times p\leq\sqrt[3] \frac np \times p$
当$p > \sqrt[4] n$时，显然分解出的三个数为它的三个质因子,成立
否则$a\times p\leq\sqrt[3]\frac n{\sqrt[4] n}\times\sqrt[4]n=\sqrt n$
证毕

于是乎，对于每次询问就可以把一个数分解
然后第一次暴力取一下膜
值域就变为了$O(\sqrt v)$
于是就可以打一个$O(\sqrt v)\times O(\sqrt v)$的表
$O(v)-O(1)$

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
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int maxn = 5000, v = 1000000, radio = 1000;
int a[maxn + 10], b[maxn + 10], n, ans;
int np[v + 10], prime[v + 10], cnt;
int k[v + 10][3];
int _gcd[radio + 10][radio + 10];
inline int gcd(int a, int b) {
    int g = 1;
    for(int tmp, i = 0; i < 3; i++) {
        if(k[a][i] > radio) {
            if(b % k[a][i] == 0) tmp = k[a][i];
            else tmp = 1;
        }
        else tmp = _gcd[k[a][i]][b % k[a][i]];
        b /= tmp;
        g *= tmp;
    }
    return g;
}
int main() {
    k[1][0] = k[1][1] = k[1][2] = 1;
    np[1] = 1;
    for(int i = 2; i <= v; i++) {
        if(!np[i]) prime[++cnt] = i, k[i][2] = i, k[i][1] = k[i][0] = 1;
        for(int j = 1; prime[j] * i <= v; j++) {
            np[i * prime[j]] = 1;
            int *tmp = k[i * prime[j]];
            tmp[0] = k[i][0] * prime[j];
            tmp[1] = k[i][1];
            tmp[2] = k[i][2];
            if(tmp[1] < tmp[0]) swap(tmp[1], tmp[0]);
            if(tmp[2] < tmp[1]) swap(tmp[2], tmp[1]);
            if(i % prime[j] == 0) break;
        }
    }
    for(int i = 1; i <= radio; i++) _gcd[i][0] = _gcd[0][i] = i;
    for(int _max = 1; _max <= radio; _max++)
        for(int i = 1; i <= _max; i++)
            _gcd[i][_max] = _gcd[_max][i] = _gcd[_max % i][i];
    // for(int i = 1; i <= 10; i++)
        // for(int j = 1; j <= 10; j++) printf("gcd(%d, %d) = %d\n", i, j, _gcd[i][j]);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", a + i);
    for(int i = 1; i <= n; i++) scanf("%d", b + i);
    for(int i = 1; i <= n; i++) {
        int now = 1, ans = 0;
        for(int j = 1; j <= n; j++) {
            now = 1ll * now * i % mod;
            ans = (ans + 1ll * gcd(a[i], b[j]) * now) % mod;
        }
        printf("%d\n", ans);
    }
    return 0;
}