[GESP202412 五级] 奇妙数字 题解

解题思路引用

FJ_EYoungOneC的解法

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

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

假设数字 n 含有 9 个因子 2，那么可以凑出 21,22,23，共三个数。

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

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

code

#include<bits/stdc++.h>
typedef long ll;
using namespace std;
ll x;
int cc(int x){int res=0,k=1;while(x>=k){res++;x-=k++;}return res;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>x;ll sum=0;for(int i=2;i<=x/i;++i){int cnt=0;while(x%i==0){x/=i;cnt++;}if(cnt){sum+=cc(cnt);}} if(x>1)sum++;cout<<sum;return 0;//华丽结束
}//完结散花