[数学][大整数质因数分解] codeforces1033D Divisors

思路简单，就是求出来结果的所有质因数的指数+1乘起来就行了。

首先由于题目的要求这里读入的ai只有两种情况，要么ai=p*q是两个不相等素数的乘积，要么ai=p^k，其中k取2，3，4。显然后一种情况很容易处理，但是第一种就有些难受了，直接的想法是用一些优秀的O(N^(1/4))的非完美大整数分解算法（这个看tutorial的评论区神仙各有千秋）。但是由于第一类的数只能分解成两个质因数，而且我们最后要的是质因数的指数而不需要关心质因数本身是多少，所以就有了更好的策略：如果一个数字的质因数在其他数字中出现过，那么一定可以通过gcd求出来，这时候等于说另一个质因数直接一除也能求出来，等于这个ai就完全解决了，像第二种情况一样加到map里即可；如果说这个数的俩质因数都没有在其他数字中出现过那么我们肯定不能求出来这俩数字是多少了，但是我们可以知道出现了俩独特的质因数，他出现且仅出现在所有aj==ai里，那么我们可以把ai直接存进map里，存起来他对应的加了多少次，另外要单独开一个set记录下来哪些ai是这样的ai，最后计算的时候如果是这样的ai的话就乘以(1+map值)的平方就可以了。

所以说一定要分析所给数据的性质，他的约束是解题的难点但同时也可能是解题的突破口。
写的时候还有一点弄错了就是把哥德巴赫猜想和这个搞混了。。那个是+这个是*，而且哥德巴赫猜想在1e18的范围内一定是有一个小的和一个大的，这个小的不超过1e5好像，所以那个是只需要枚举小的然后判断大的是否为质数即可。

#include

using namespace std;
typedef long long LL;
const int maxn=500+4;
const int mod=998244353;

LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}

LL a[maxn];
map mp;
setFS;
bool vis[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("1.txt","r",stdin);
    //freopen("2m.txt","w",stdout);
    int n;
    cin>>n;
    LL tmp,st;
    double dt,fc=1.0/3.0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        tmp=a[i];
        dt=1.0*tmp;
        st=(LL)(pow(dt,0.25)+0.5);
        if(st*st*st*st==tmp)
        {
            mp[st]+=4;
            vis[i]=1;
            continue;
        }
        st=(LL)(pow(dt,0.5)+0.5);
        if(st*st==tmp)
        {
            mp[st]+=2;
            vis[i]=1;
            continue;
        }
        st=(LL)(pow(dt,fc)+0.5);
        if(st*st*st==tmp)
        {
            mp[st]+=3;
            vis[i]=1;
            continue;
        }

    }
    LL ans=1;
    for(int i=1;i<=n;i++)if(!vis[i])
    {
        //cout<1)
            {
                mp[t1]++;
                mp[a[i]/t1]++;
                flag=1;
                break;
            }
        }
        if(!flag)
        {
            mp[a[i]]++;//error1
            FS.insert(a[i]);
        }
    }
    for (map::iterator it=mp.begin(); it!=mp.end(); it++)
    {
        if(FS.find(it->first)==FS.end())
            ans=(ans*(1+it->second))%mod;
        else
        {
            ans=(ans*(1+it->second))%mod;
            ans=(ans*(1+it->second))%mod;
        }

    }
    cout<