个人感觉自己写的算法的时间复杂度是对的

但很显然我的代码不这么认为

详见代码与注释

#include<bits/stdc++.h>
#define ll long long
#define re register
#define gin(x,y) (x<y?x:y)
#define ord(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;
inline int read(){
	re char c=getchar(); re int x=0,f=1;
	while(c<'0'||c>'9') { c=getchar();if(c=='-') f=-1; }
	while(c>='0'&&c<='9') { x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return x*f;
}
const int N=5e3+20,M=1e3;const ll P=998244353;//M是sqrt(V)  V是值域 
int n,a[N],b[N],d[M+20][M+20],h[M*M+40];
bool pri[M*M+20];
struct D{ int a,b,c; void st(){ if(a>b) swap(a,b); if(a>c) swap(a,c); if(b>c) swap(b,c); } } f[M*M];
inline int gcd(int x,int y){//这个函数理论上时间复杂度应该是O(1) 
//	if(y<x) swap(x,y);
//	if(y%x==0) return x;
//	if(!pri[x]||!pri[y]) return 1;
//	y=y%x; return d[x][y];
	return (!pri[x])?(y%x==0?x:1):d[x][y%x]; 
}
signed main(){
	n=read();//读入 或许我的快读太慢了? 
	ord(i,1,n) a[i]=read();
	ord(i,1,n) b[i]=read();
	
	ord(i,1,M) ord(j,0,i){//直接预处理值域在sqrt(V)内的gcd 复杂度 O(V) 
		if(j==0) d[j][i]=d[i][j]=i;
		else d[j][i]=d[i][j]=d[j][i%j];
	} 
	
	//判断质数并且处理数的分解  h[i]表示i的最小质因数 复杂度是远小于O(V logV)的 
	ord(i,1,M*M) h[i]=i;
	f[1]=(D){1,1,1};
	ord(i,2,M*M) if(!pri[i]){
		f[i]=(D){1,1,i};
		ord(j,i,M*M/i) pri[j*i]=1,h[j*i]=min(h[j*i],i);
	} 
	ord(i,2,M*M) if(pri[i]) f[i]=f[i/h[i]],f[i].a*=h[i],f[i].st(); 
	
	ll v,u,t,g,ans;//处理结果 O(n^2) 
	ord(i,1,n){
		g=1,ans=0;
		ord(j,1,n){
			v=1,u=b[j],g=g*i%P;
			t=gcd(f[a[i]].a,u);u/=t,v*=t;
			t=gcd(f[a[i]].b,u);u/=t,v*=t;
			t=gcd(f[a[i]].c,u);u/=t,v*=t;
			ans=(ans+g*v%P)%P;
		}
		printf("%lld\n",ans);
	}
	return 0;
}