ABC445E TLE问复杂度

#include<bits/stdc++.h> 
#define int long long
using namespace std;
typedef long long ll;
const int N=5e5+10,M=1e7+10,P=998244353;
int n,a[N],mpri[M],pri[M],tot;
struct Node{
	int ma1,cnt1,ma2;
};
void init(){
	mpri[0]=mpri[1]=1;
	for(int i=2;i<=M-10;i++){
		if(!mpri[i]){
			mpri[i]=i;
			pri[++tot]=i;
		}
		for(int j=1;j<=tot;j++){
			if(pri[j]>mpri[i]||i*pri[j]>M-10)break;
			mpri[i*pri[j]]=pri[j];
		}
	}
}
int qp(int a,int b){
	int res=1;
	a%=P;
	while(b){
		if(b&1)res=res*a%P;
		a=a*a%P;
		b>>=1; 
	}
	return res;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	vector<vector<pair<int,int> > > fac(N);
	unordered_map<int,bool> mp;
	unordered_map<int,Node> info;
	for(int i=1;i<=n;i++){
		int x=a[i];
		while(x>1){
			int p=mpri[x],e=0;
			while(x%p==0)x/=p,e++;
			fac[i].push_back({p,e});
			if(mp.find(p)==mp.end()){
				mp[p]=1;
				info[p]={-1,-1,0};
			}
			if(e>info[p].ma1)info[p].ma2=info[p].ma1,info[p].ma1=e,info[p].cnt1=1;
			else if(e==info[p].ma1)++info[p].cnt1;
			else if(e>info[p].ma2)info[p].ma2=e;
		}
	}
	for(auto& it:mp){
		int p=it.first;
		if(info[p].ma2==-1)info[p].ma2=0;
	}
	int lcm=1;
	for(auto& it:info){
		int p=it.first;
		Node t=it.second;
		lcm=lcm*qp(p,t.ma1)%P;
	}
	for(int i=1;i<=n;i++){
		int res=lcm;
		for(auto& it:fac[i]){
			int p=it.first,e=it.second;
			Node t=info[p];
			if(e==t.ma1&&t.cnt1==1){
				res=res*qp(p,t.ma2)%P;
				res=res*qp(p,P-1-t.ma1)%P;
			}
		}
		cout<<res<<' ';
	}
	cout<<'\n';
}
signed main(){
	init();
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T;cin>>T;
	while(T--){solve();}
    return 0;
}