题解：B4070 [GESP202412 五级] 奇妙数字

FJ_EYoungOneC · 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;
}