一种 O( 值域 )时间预处理 O(1) 时间求最大公约数( gcd )的算法

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int mod=998244353;
const int maxn=5050;
const int maxm=1000;
const int maxx=1000100;
int prime[maxx],fac[maxx][3],gcd[maxm+10][maxm+10];
int a[maxn],b[maxn],cnt,n;
bool ha[maxx];

void Prime(void)
{
    fac[1][0]=fac[1][1]=fac[1][2]=1;
    ha[1]=true;
    for(int i=1;i<maxx;i++)
    {
        if(!ha[i])
        {
            prime[cnt++]=i;
            fac[i][0]=fac[i][1]=1;
            fac[i][2]=i;
        }
        for(int j=0;j<cnt&&i*prime[j]<maxx;j++)
        {
            int now=i*prime[j];
            ha[now]=true;
            fac[now][0]=fac[i][0]*prime[j];
            fac[now][1]=fac[i][1];
            fac[now][2]=fac[i][2];
            if(fac[now][0]>fac[now][1]) swap(fac[now][0],fac[now][1]);
            if(fac[now][1]>fac[now][2]) swap(fac[now][1],fac[now][2]);
            if(i%prime[j]==0) break;
        }
    }
    for(int i=0;i<=maxm;i++) gcd[i][0]=gcd[0][i]=i;
    for(int i=1;i<=maxm;i++)
        for(int j=1;j<=i;j++)
            gcd[i][j]=gcd[j][i]=gcd[j][i%j];
}

int gg(int a,int b)
{
    int ans=1;
    for(int i=0;i<=2;i++)
    {
        int now=0;
        if(fac[a][i]>maxm)
        {
            if(b%fac[a][i]==0) now=fac[a][i];
            else now=1;
        }
        else now=gcd[fac[a][i]][b%fac[a][i]];
        b/=now;
        ans*=now;
    }
    return ans;
}

int main(void)
{
    Prime();
    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=(ll)now*i%mod;
            ans=(ans+(ll)gg(a[i],b[j])*now%mod)%mod;
        }
        printf("%d\n",ans);
    }
    return 0;

}