数论，质因数，gcd——cf1033D 好题！

直接筛质数肯定是不行的

用map<ll,ll>来保存质因子的指数

考虑只有3-5个因子的数的组成情况

必定是a=pq or a=p*p or a=p*p*p or a=p*p*p*p

先用二分判后面三种情况

然后判第一种情况

由于不知道pq，而且无法直接求，我们间接用 d=gcd(a[i],a[j]) 来求

如果1<d<a[i],那么a[i]两个因数就可以确定是d,a[i]/d

反之a[i]两个因数未出现过，pq直接计算到贡献里去

但是可能有和a[i]相等的数，所以我们不先计算这样pq的数量，而是另外开一个map<ll,ll>来计算像a[i]这样的不能直接求出因子的数及其个数

然后求答案时再和另一个map分开统计，相乘

#include<bits/stdc++.h>

#include<map>

using namespace std;

#define ll long long

#define mod 998244353

map<ll,ll>mp;

map<ll,ll>::iterator it;

int n,tot;

ll a[];

ll calc4(ll x){

    ll l=,r=,mid;

    while(l<=r){

        mid=l+r>>;

        ll t=mid*mid*mid*mid;

        if(t==x)return mid;

        else if(t>x)r=mid-;

        else l=mid+;

    }

    return -;

}

ll calc3(ll x){

    ll l=,r=,mid;

    while(l<=r){

        mid=l+r>>;

        ll t=mid*mid*mid;

        if(t==x)return mid;

        else if(t>x)r=mid-;

        else l=mid+;

    }

    return -;

}

ll calc2(ll x){

    ll l=,r=,mid;

    while(l<=r){

        mid=l+r>>;

        ll t=mid*mid;

        if(t==x)return mid;

        else if(t>x)r=mid-;

        else l=mid+;

    }

    return -;

}

map<ll,ll>has;

int main(){

    cin>>n;

    for(int i=;i<=n;i++)cin>>a[i];

    for(int i=;i<=n;i++){

        ll p=calc4(a[i]);

        if(p!=-){mp[p]+=;continue;}

        p=calc3(a[i]);

        if(p!=-){mp[p]+=;continue;}

        p=calc2(a[i]);

        if(p!=-){mp[p]+=;continue;}

        int flag=;

        for(int j=;j<=n;j++){//找p

            if(i==j)continue;

            ll d=__gcd(a[i],a[j]);

            if(d!= && d!=a[j]){

                mp[d]++;mp[a[i]/d]++;

                flag=;break;

            }

        }

        if(flag==)has[a[i]]++;//找不到p，就把a[i]存下来

    }

    ll ans=;

    for(it=has.begin();it!=has.end();it++){//计算第二个map的贡献

        ans=ans*(it->second+)%mod*(it->second+)%mod;

    }

    for(it=mp.begin();it!=mp.end();it++){//计算第一个map的贡献

        ans=ans*(it->second+)%mod;

    }

    cout<<ans<<endl;

}