奇妙数字
C++
中等
GESP五级真题
#数论#质因数分解
题目描述
题面描述
小杨认为一个数字是奇妙数字当且仅当，其中为任意质数且为正整数。例如，，所以8是奇妙数字，而6不是。
对于一个正整数，小杨想要构建一个包含个奇妙数字的集合，使其满足以下条件：
- 集合中不包含相同的数字。
- 是的因子（即这个数字的乘积是的因子）。
小杨希望集合包含的奇妙数字尽可能多，请你帮他计算出满足条件的集合最多包含多少个奇妙数字。
输入格式
第一行包含一个正整数，含义如题面所示。
输出格式
输出一个正整数，代表满足条件的集合最多包含的奇妙数字个数。
样例1
输入：
128
输出：
3
样例解释
关于本样例，符合题意的一个包含3个奇妙数字的集合是。首先，因为，，，所以2,4,8均为奇妙数字。同时，是128的因子。
由于无法找到符合题意且同时包含4个奇妙数字的集合，因此本样例的答案为3。
样例2
输入：
12
输出：
2
样例解释
12的质因数分解为，符合条件的集合可以是，共2个奇妙数字，无法找到更多元素的合法集合。
数据范围
对于全部数据，保证有 。
时间限制
1.0 s
内存限制
512.0 MB
💡 查看提示（先自己想一想再看）
核心考察质因数分解、贪心思想。解题步骤：1. 对n进行质因数分解，统计每个质数的指数；2. 对于每个质数的指数k，计算最多能拆分成多少个不同正整数的和（如k=3可拆为1+2，对应2个元素？不对，k=7拆为1+2+3得3个元素和为6，剩余1无法新增，所以calc(k)求的是最大t使得t*(t+1)/2 ≤k）；3. 将所有质数对应的结果相加即为答案。注意n的范围到1e12，质因数分解只需要枚举到sqrt(n)即可。
讨论（0）
登录后即可参与讨论 去登录 →