[Lyft Level 5 Challenge 2018 – Elimination Round][Codeforces 1033D. Divisors]

题目链接：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 ;
}