Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define tag "MULDIV"
#define forinc(i,a,b) for(int i=a;i<=b;i++)
#define checkfile(FiLeNaMe) { if(fopen(FiLeNaMe".inp","r")) freopen(FiLeNaMe".inp","r",stdin),freopen(FiLeNaMe".out","w",stdout); }
///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
int T;
int n;
int pre[10000007];
#define somod 998244353

void enter(){
    forinc(i,2,1e7) pre[i]=i;

    for(int i=2;i*i<=1e7;i++) if(pre[i]==i) for(int j=i*i;j<=1e7;j+=i) if(pre[j]==j) pre[j]=i;
}


int cntdiv(int x){
    int ans=1;

    while(x>1){
        int y=pre[x];
        int p=0;

        while(x%y==0) ++p,x/=y;

        ans*=(p+1);
    }

    return ans;
}

int powmod(int a,int b){
    int64_t ans=1;
    int64_t x=a;

    for(int i=b;i>0;i>>=1){
        ans = i&1 ? ans*x%somod : ans;
        x = x*x%somod;
    }

    return ans;
}

void call(){
    cin>>n;

    int x=cntdiv(n);

    int64_t ans=powmod(n,x>>1);

    if(x&1) ans=ans*int(sqrt(n))%somod;

    cout<<ans<<"\n";
}

void solve(){
    cin>>T;
    forinc(i,1,T) call();
}

signed main(){
    checkfile(tag);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    enter();
    solve();

    return 0;
}