B4070 [GESP202412 五级] 奇妙数字
题目背景
对应的选择、判断题：https://ti.luogu.com.cn/problemset/1169
题目描述
小杨认为一个数字 \(x\) 是奇妙数字当且仅当 \(x=p^a\)，其中 \(p\) 为任意质数且 \(a\) 为正整数。例如，\(8=2^3\)，所以 \(8\) 是奇妙的，而 \(6\) 不是。
对于一个正整数 \(n\)，小杨想要构建一个包含 \(m\) 个奇妙数字的集合 \(\{x_1,x_2,\cdots,x_m\}\)，使其满足以下条件：
- 集合中不包含相同的数字。
- \(x_1\times x_2\times \cdots\times x_m\) 是 \(n\) 的因子（即 \(x_1,x_2,\cdots,x_m\) 这 \(m\) 个数字的乘积是 \(n\) 的因子）。
小杨希望集合包含的奇妙数字尽可能多，请你帮他计算出满足条件的集合最多包含多少个奇妙数字。
输入格式
第一行包含一个正整数 \(n\)，含义如题面所示。
输出格式
输出一个正整数，代表满足条件的集合最多包含的奇妙数字个数。
输入输出样例 #1
输入 #1
128
输出 #1
3
说明/提示
样例解释
关于本样例，符合题意的一个包含 \(3\) 个奇妙数字的集合是 \(\{2,4,8\}\)。首先，因为 \(2=2^1\)，\(4=2^2\)，\(8=2^3\)，所以 \(2,4,8\) 均为奇妙数字。同时，\(2\times 4\times 8=64\) 是 \(128\) 的的因子。
由于无法找到符合题意且同时包含 \(4\) 个奇妙数字的集合，因此本样例的答案为 \(3\)。
数据范围
对于 \(100\%\) 的数据，保证 \(2\le n\le 10^{12}\)。
| 子任务编号 | 得分占比 | \(n\) |
|---|---|---|
| \(1\) | \(20\%\) | \(\le 10\) |
| \(2\) | \(20\%\) | \(\le 1\,000\) |
| \(3\) | \(60\%\) | \(\le 10^{12}\) |
#include<bits/stdc++.h>
using namespace std;
long long n;
long long ans=0;
long long find2(long long x) {long long t=1,q=0;while (x>=t) {q=q+1;x=x-t;t=t+1;}return q;
}void find() {for(long long i=2;i*i<=n;++i) {long long sum=0;while (n%i==0) {sum++;n=n/i;}if (sum) {ans+=find2(sum);}}if (n!=0) {ans++;}
}int main() {cin>>n;find();cout<<ans<<endl;return 0;
}