题解 P5435 【【模板】快速 GCD】

hehezhou · 2019-07-30 16:30:48 · 题解

感谢@Duan2baka 指出一处错误

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

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

证明一下为什么是对的
考虑归纳法
只需证明把p乘上最小的数后得到的结果一定不大于\sqrt n

当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)的表

#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;
}