一种 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;
}