[Lyft Level 5 Challenge 2018

题目大意：给定(n)个数(a_i)，每个数的约数个数为3到5个，求(prod_{i=1}^{n}a_i)的约数个数。其中(1 leq n leq 500 , 1 leq a_i leq 2cdot 10^{18})。

题解：考虑约数个数公式，可以发现对于任意的(a_i)，有(a_i=left{egin{matrix}
p^2\
p^3\
p^4\
p_1cdot p_2
end{matrix} ight.)

其中前三种情况可以直接通过二分来找出时候有满足条件的(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 eq i))，有(gcd(c_i,a_j)=left{egin{matrix}
1\
c_i
end{matrix} ight.)，即(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=1,r=n;
    while(l<r)
      {
      LL mid=(l+r+1)/2ll;
      LL res=1,K=k;
      while(K--)
        {
        if(res>INF/mid)
          {res=INF;break;}
        res*=mid;
        }
      if(res>n)r=mid-1;
      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=1;i<=n;i++)
      {
      LL xx=0;
      scanf("%I64d",&a[i]);
      for(LL k=4;k>=2;k--)
        {
        LL p=Sqrt(a[i],k);
        LL res=1,K=k;
        while(K--)res*=p;
        if(res==a[i]){f[p]+=k,xx=1;break;}
        }
      if(xx)continue;
      b[i]=a[i];
      }
    for(LL i=1;i<=n;i++)if(b[i])
      {
      LL xx=0;
      for(LL j=1;j<=n;j++)
        {
        if(j==i)continue;
        LL g=gcd(b[i],a[j]);
        if(g==1 || g==b[i])continue;
        xx=1,f[g]++,f[b[i]/g]++;
        break;
        }
      if(!xx)c[i]=b[i];
      }
    LL ans=1;
    for(LL i=1;i<=n;i++)if(c[i])
      {
      LL cnt=2;
      for(LL j=1;j<=n;j++)
        if(c[i]==c[j] && j!=i)cnt++,c[j]=0;
      ans*=cnt*cnt,ans%=MOD;
      }
    for(auto p:f)ans*=p.second+1,ans%=MOD;
    printf("%I64d
",ans);
    fflush(stdout);
    return 0;
}

View Code