题目大意:给定(n(1leq nleq500))个数(a_1,a_2cdots,a_n(1leq a_ileq2cdot10^{18})),每个数有(3sim5)个因数,求(prod_{i=1}^{n}a_i)的因数个数
这道题是一个交互题(虽说并不觉得有交互的必要...可能只是为了(hack)或者造数据方便吧),非常纯的数((du))学((liu)),题目难度不在于结论,而在于代码实现
小学数学告诉我们以下结论:一个正整数(x)可以被分解成唯一形式(x=p_{1}^{a_{1}}cdot p_{2}^{a_{2}}cdot cdots cdot p_{k}^{a_{k}}(p_i ext{为质数})),(x)的因数个数为(prod_{i=1}^{k}(a_i+1)).所以这道题的本质是质因数分解.
对于一个数(x)进行质因数分解最快的方式是枚举(2simsqrt{x})的质数(p)判断(p)是否能整除(x)进行分解,但是题目数据范围(a_ileq10^{18}),如果要对(a_i)直接质因数分解需要枚举(2sim10^9)内所有质数,若按照这种思路还需要预处理(10^9)内的质数表.
但是这样做并不可行,(10^9)内的质数表即使用线性筛也无法在(1s)和(256M)的限制内完成.此时注意到题目上还有未使用到的条件:每个数有(3sim5)个因数.所以此题唯一的入手点就是这个具有奇特性质的条件.
考虑一个数(x)有(3sim5)个因数可能的特殊性质,发现(x)有((1)p_1cdot p_2,(2)p_1^2,(3)p_1^3,(4)p_1^4)四种可能的分解形式,对于((2)(3)(4))三种分解形式,我们可以考虑二分求出(p_1)((cmath)并不支持求(sqrt[3]{x},sqrt[4]{x})),如果满足((2)(3)(4))中任意一种分解,那么直接计数即可,如果三种分解形式都不满足,那么考虑对于(p_1cdot p_2)形式的数的分解,如果(p_1,p_2)的次数都为(1)那么可以不分解这样的(x),直接乘((cnt+1)^2),如果(p_1,p_2)的次数有至少一个不为(1),那么对于(x)一定存在一个数(y(y
eq x))使得(gcd(x,y)>1),此时的(gcd(x,y))就是(x,y)的一个质因数,也即(x,y)都完成了质因数分解.至此所有可分解的数都完成了质因数分解,不可分解的数都满足两个质因数次数为(1),所以剩下的只需要求(prod_{i=1}^{k}(a_i+1))即可.
下面放(AC)代码(downarrowdownarrowdownarrow)
#include<cstdio>//CF1033D
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<map>
using namespace std;
const int MOD=998244353;
int n;
long long a[502];
map<long long,long long>mp,mmp;
long long gcd(long long u,long long v){
if(v==0){
return u;
}
return gcd(v,u%v);
}
long long bs2(long long l,long long r,long long u){
if(l==r){
return l;
}
long long mid=(l+r)>>1;
if(mid*mid<u){
return bs2(mid+1,r,u);
}
else{
return bs2(l,mid,u);
}
}
long long bs3(long long l,long long r,long long u){
if(l==r){
return l;
}
long long mid=(l+r)>>1;
if(mid*mid*mid<u){
return bs3(mid+1,r,u);
}
else{
return bs3(l,mid,u);
}
}
long long bs4(long long l,long long r,long long u){
if(l==r){
return l;
}
long long mid=(l+r)>>1;
if(mid*mid*mid*mid<u){
return bs4(mid+1,r,u);
}
else{
return bs4(l,mid,u);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;i++){
long long rep;
rep=bs4(1,40000,a[i]);
if(rep*rep*rep*rep==a[i]){
mp[rep]+=4;
continue;
}
rep=bs3(1,1300000,a[i]);
if(rep*rep*rep==a[i]){
mp[rep]+=3;
continue;
}
rep=bs2(1,1500000000,a[i]);
if(rep*rep==a[i]){
mp[rep]+=2;
continue;
}
bool flag=false;
for(auto ite:mp){
if(a[i]%ite.first==0){
mp[ite.first]++;
mp[a[i]/ite.first]++;
flag=true;
break;
}
}
if(!flag){
for(auto ite2:mmp){
if(ite2.first==a[i]){
mmp[a[i]]++;
flag=true;
break;
}
long long g=gcd(a[i],ite2.first);
if(g>1){
mp[g]+=ite2.second+1;
mp[a[i]/g]++;
mp[ite2.first/g]+=ite2.second;
mmp[ite2.first]=0;
flag=true;
break;
}
}
if(!flag){
mmp[a[i]]++;
}
}
}
for(auto ite2:mmp){
for(auto ite:mp){
if(ite2.first%ite.first==0){
mp[ite.first]+=ite2.second;
mp[ite2.first/ite.first]+=ite2.second;
mmp[ite2.first]=0;
break;
}
}
}
long long ans=1;
for(auto ite:mp){
ans*=(ite.second+1);
ans%=MOD;
}
for(auto ite:mmp){
ans*=(ite.second+1);
ans%=MOD;
ans*=(ite.second+1);
ans%=MOD;
}
printf("%lld
",ans);
fflush(stdout);
return 0;
}