【题解】洛谷 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;
}

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

于2019年9月30日由skydogli发布

解题思路：

代码

1 条评论

skydogli · 2019年10月7日 10:00 下午

发表回复取消回复

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

于2019年9月30日由skydogli发布

解题思路：

代码

1 条评论

skydogli · 2019年10月7日 10:00 下午

发表回复 取消回复

发表回复取消回复