自动搬运

查看原文

来自洛谷，原作者为

	FJ_EYoungOneC 这个人很勤快，但是他并不想留下什么

搬运于2025-08-24 21:16:52，当前版本为作者最后更新于2024-12-13 16:43:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路

数字 $x$ 是奇妙数字当且仅当 $x=p^a$ 其中 $p$ 为任意质数且 $a$ 为正整数。

那么我们可以对 $n$ 进行质因子分解，并统计每个质数因子的个数。

假设数字 $n$ 含有 $9$ 个因子 $2$，那么可以凑出 $2^1, 2^2, 2^3$，共三个数。

那么我们需要计算的就是 $1+2+\dots+k >$ 因子的个数时 $k$ 的最小解，那么 $k-1$ 就是答案。

我们可以使用二分 $+$ 等差数列求和公式进行计算，由于数据范围较小（long long 范围以内，质因子最多个数的即为 $2^{63}$），直接模拟即可。

AC_Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

LL x;

int calc(int x)
{
    int res = 0, k = 1;
    while (x >= k)
    {
        res ++;
        x -= k ++;
    }
    return res;
}

int main()
{
    cin >> x;
    
    LL res = 0;
    for (int i = 2; i <= x / i; ++ i )
    {
        int cnt = 0;
        while (x % i == 0)
            x /= i, cnt ++;
        if (cnt)
            res += calc(cnt);
    }
    
    if (x > 1)
        res ++;
    
    cout << res << endl;
    
    return 0;
}