题目链接：1033D - Divisors
题目大意：给定\(n\)个数\(a_i\)，每个数的约数个数为3到5个，求\(\prod_{i=1}^{n}a_i\)的约数个数。其中\(1 \leq n \leq 500 , 1 \leq a_i \leq 2\cdot 10^{18}\)。
题解：考虑约数个数公式，可以发现对于任意的\(a_i\)，有\(a_i=\left\{\begin{matrix}
p^2\\
p^3\\
p^4\\
p_1\cdot p_2
\end{matrix}\right.\)
其中前三种情况可以直接通过二分来找出时候有满足条件的\(p\)，若存在符合条件的\(p\)，则用\(map\)记录更新\(p\)的指数，否则\(a_i\)一定为两不同质数的积，将其记录到\(b_i\)中
接下来对于每个\(b_i\)，遍历所有的\(a_j\)，若存在这样的\(j\)，使得\(1<gcd(b_i,a_j)<b_i\)，则\(gcd(b_i,a_j)\)必为其中的一个质数，从而可以求出\(p_1,p_2\)的值并更新其指数，若找不到这样的\(j\)，将其记录到\(c_i\)中
可以发现，在\(C\)中的数一定是由两个不同质数组成的，且没有数和他恰好有一个质因子。因此对于任意的\(a_j(j\neq i)\)，有\(gcd(c_i,a_j)=\left\{\begin{matrix}
1\\
c_i
\end{matrix}\right.\)，即\(a_j\)与\(c_i\)互质或者与之相等。因此这时只需要对每个不同的\(c_i\)判断有多少数与他相同并计算贡献就好。由于没有其它的数与\(c_i\)有相同质因子，因此\(c_i\)的两个质因子肯定是没有出现过的，设与\(c_i\)相同的数的个数为\(cnt\)，将答案乘上\((cnt+1)\cdot (cnt+1)\)就好了。
#include<bits/stdc++.h>
using namespace std;
#define N 501
#define LL long long
#define MOD 998244353
LL INF=9e18;
LL n,a[N],b[N],c[N];
map<LL,LL>f;
LL Sqrt(LL n,LL k)
{
LL l=,r=n;
while(l<r)
{
LL mid=(l+r+)/2ll;
LL res=,K=k;
while(K--)
{
if(res>INF/mid)
{res=INF;break;}
res*=mid;
}
if(res>n)r=mid-;
else l=mid;
}
return l;
}
LL gcd(LL x,LL y){return y?gcd(y,x%y):x;}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
LL xx=;
scanf("%I64d",&a[i]);
for(LL k=;k>=;k--)
{
LL p=Sqrt(a[i],k);
LL res=,K=k;
while(K--)res*=p;
if(res==a[i]){f[p]+=k,xx=;break;}
}
if(xx)continue;
b[i]=a[i];
}
for(LL i=;i<=n;i++)if(b[i])
{
LL xx=;
for(LL j=;j<=n;j++)
{
if(j==i)continue;
LL g=gcd(b[i],a[j]);
if(g== || g==b[i])continue;
xx=,f[g]++,f[b[i]/g]++;
break;
}
if(!xx)c[i]=b[i];
}
LL ans=;
for(LL i=;i<=n;i++)if(c[i])
{
LL cnt=;
for(LL j=;j<=n;j++)
if(c[i]==c[j] && j!=i)cnt++,c[j]=;
ans*=cnt*cnt,ans%=MOD;
}
for(auto p:f)ans*=p.second+,ans%=MOD;
printf("%I64d\n",ans);
fflush(stdout);
return ;
}