A29868. 奇妙数字
填空题
困难
知识点
题目描述
奇妙数字
时间限制：1.0 s 内存限制：512.0 MB
题目描述
小杨认为一个数字x是奇妙数字当且仅当x=pa，其中p为任意质数且a为正整数。例如，8=2*2*2，所以8是奇妙数字，而6不是。
对于一个正整数 n，小杨想要构建一个包含m个奇妙数字的集合{x1,x2,,,,xm}，使其满足以下条件：
集合中不包含相同的数字。
x1,x2,,,,xm 是 n 的因子（即x1,x2,,,,xm 这m个数字的乘积是n的因子）。
小杨希望集合包含的奇妙数字尽可能多，请你帮他计算出满足条件的集合最多包含多少个奇妙数字。
输入格式
第一行包含一个正整数n，含义如题目所示。
输出格式
输出一个正整数，代表满足条件的集合最多包含的奇妙数字个数。
输入样例
128
输出样例
3
参考答案
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
ll calc(ll x) {
int ans = 0;
ll tmp=1;
while(x>=tmp) {
ans++;
x-=tmp;
tmp++;
}
return ans;
}
int main() {
ll n;
cin>>n;
ll ans = 0;
for (ll i=2;i*i<=n;i++) {
if(n%i==0) {
int cnt = 0;
while(n%i==0) {
cnt++;
n/=i;
}
ans+=calc(cnt);
}
}
if(n!=1) {
ans+=calc(1);
}
cout<<ans<<"\n";
}
上一题
下一题