【题解】洛谷 5435[模板] 快速 GCD

对于 $gcd$的询问，设值域为 $V$，询问次数为 $Q$, 有一种奇奇怪怪的时空复杂度都是 $O(V+Q)$，即 $O(V)——O(1)$的做法。

题面

解题思路：

把值域内的数 $x$都分解成 $3$个都不大于 $\sqrt x$的数相乘 (允许出现大于 $\sqrt x$的质数），步骤如下：

• 处理完所有小于 $x$的数
• 找到 $x$最小的质因子 $p$
• 将 $\frac{x}{p}$分解的 $3$个数赋值入 $x$中，并把最小的数 $a$乘上 $p$

我们只需要证明这个最小的数 $a \times p\leq x$或 $a \times p$是质数，因为其它 2 个数不是大质数就是小于 $\sqrt{\frac{x}{p}}$, 肯定符合条件。
当 $a=\not1$时，因为 $p$是 $x$的最小质因子，所以 $p\leq a$, 又因为 $a\leq \sqrt[3]{\frac{x}{p}}$，
所以 $p\leq{ \sqrt[3]{\frac{x}{p}}}$
p 非负，所以把根号去掉变成
$$ p^3\leq \frac{x}{p}$$
$$p^4\leq x$$
另外，$p\times \sqrt[3]{\frac{x}{p}}$明显是递增的（你也可以在这里直观感受一下
当 p 取最大值 $\sqrt[4]{x}$时，$a\times p\leq \sqrt[4]{x}\times \sqrt[3]{\frac{x}{\sqrt[4]{x}}}=\sqrt[3]{x\times \sqrt[4]{x^2}}=\sqrt[3]{x^{\frac{3}{2}}}=\sqrt{x}$
特殊的，当 $a=1$时，$p$显然是质数，即使大于 $\sqrt{x}$满足我们要求的性质

同时，上面的操作明显可以用线性筛完成

处理完之后，所有数基本都在 $\sqrt{V}$以内了，那么我们就可以打个 $\sqrt{V}\times\sqrt{V}$的 $gcd$的表，每次求 $gcd$是可以 $O(1)$的,$gcd[i][j]=gcd[j][i]=gcd[i\ \ mod\ \ j][j]$。根据辗转相除法，这显然正确。查询 2 个大数 $x,y$的 $gcd$时，找出 a 的分解的 $3$个数 $num_1,num_2,num_3$，对于每个 $num$，如果是质数直接判断能不能整除 b，否则求 $gcd[num_i][b \ \ mod \ \ num_i]$，然后让 $b$除以这个数就行了。

代码

#include<bits/stdc++.h>
using namespace std;
#define rint register int
#define MN 5005
#define Maxn 1000005
#define Mod 998244353
#define BK 1005
#define LL long long
int n,a[MN],b[MN],Max,num[Maxn][3],GCD[BK][BK],table,vis[Maxn],p[Maxn],cnt;
inline int gcd(int x,int y){
    int res=1;
    for(int i=0;i<3;++i)
        if(num[x][i]>table){if(y%num[x][i]==0)y/=num[x][i],res*=num[x][i];}//大于表的范围，肯定是质数
            else {int tmp=GCD[num[x][i]][y%num[x][i]];res*=tmp;y/=tmp;}//y 除，答案乘
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]),Max=max(Max,a[i]);//找出值域
    for(int i=1;i<=n;++i)scanf("%d",&b[i]),Max=max(Max,b[i]);
    table=sqrt(Max);
    num[1][0]=num[1][1]=num[1][2]=1;
    for(int i=2;i<=Max;++i){
        if(!vis[i])p[++cnt]=i,num[i][0]=num[i][1]=1,num[i][2]=i;
        for(int j=1,tmp;(tmp=p[j]*i)<=Max;++j){
            vis[tmp]=1;
            num[tmp][0]=num[i][0]*p[j];
            num[tmp][1]=num[i][1];
            num[tmp][2]=num[i][2];
            if(num[tmp][0]>num[tmp][1]){
                swap(num[tmp][0],num[tmp][1]);
                if(num[tmp][1]>num[tmp][2])
                    swap(num[tmp][1],num[tmp][2]);
            }
            if(i%p[j]==0)break;//线性筛
        }
    }
    for(int i=1;i<=table;++i)GCD[i][i]=GCD[i][0]=GCD[0][i]=i;
    for(int i=1;i<=table;++i)
        for(int j=1;j<i;++j)
            GCD[i][j]=GCD[j][i]=GCD[i%j][j];//和辗转相除差不多，O（1)
    for(int i=1;i<=n;++i){
        LL now=1,ans=0,f=1;
        for(int j=1;j<=n;++j){
            f=f*i%Mod;
            ans=(ans+(LL)f*gcd(a[i],b[j]))%Mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}