题目大意
给定一个正整数\(n\),并对它进行若干次操作。
对于每次操作，选择一个正整数\(x\)，满足\(x=p^e\)且\(x\)和其它操作中用过的\(x\)不一样（每个用一次），\(x\)为n的因数。其中\(p\)为质数，\(e\)为正整数，并将\(n\)变为\(\frac{n}{x}\)
问最多操作次数。
首先对\(n\)进行质因数分解。
\[n=p_1^{e_1}\times p_2^{e_2}\times ...\times p_m^{e_m}
\]
对于每一个\(p_i^{e_i}\),可以进一步拆分为：
\[p_i^{e_i}=p_i^{a_1}\times p_i^{a_2}\times...\times p_i^{a_{k_i}}
\]
所以我们要求的就是：
\[ans=\sum_{i=1}^m k_i
\]
然后考虑怎么样让\(k_i\)最大，发现每一个\(a_i\)尽可能小的时候，\(k_i\)最大。然后就做完了。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
map<ll,ll> m;
ll tot[100005];
ll len=0;
ll n;
ll ans=0;
int main(){
// for(int i=1;i<=50;i++)
// Fuck
cin>>n;
for(ll i=2;i*i<=n;i++){
if(n%i==0)
tot[++len]=i;
while(n%i==0)
n/=i,m[i]++;
}
if(n>1)
tot[++len]=n,m[n]++;
for(int i=1;i<=len;i++){
ll now=tot[i];
for(int k=1;k<=m[now];k++){
ans++;
m[now]-=k;
}
}
printf("%lld",ans);
// for(int i=1;i<=len;i++)
// printf("%lld %lld\n",tot[i],m[tot[i]]);
return 0;
}