G5011 [GESP202412 五级] 奇妙数字 题解

知识点：质因数分解、贪心、计数。

解题思路

分解质因数，对每个指数c依次扣除1、2、3……，每能扣一次就增加答案。

为什么正确

同一质数可构造互不相同的指数，取最小的1到k所需指数总量最少，因此贪心能构造最多个数；不同质数分别贡献。

易错点

不要把指数c直接计为c次；剩余大质因子指数为1时仍贡献一次。

复杂度

时间O(√n)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin>>n;
    int ans=0;
    for(long long p=2;p*p<=n;p++) {
        if(n%p)continue;
        int c=0;
        while(n%p==0) {
            n/=p;
            c++;
        }
        for(int k=1;c>=k;k++) {
            c-=k;
            ans++;
        }
    }
    if(n>1)ans++;
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。