2024 GESP五级「奇妙数字」深度解析：高效解题代码与数学逻辑揭秘(洛谷B4070)
一、题目解读
2024年GESP（青少年编程能力等级测试）五级题目「奇妙数字」（对应洛谷平台题目B4070），要求选手根据特定规则计算输入数字的“奇妙值”。题目核心在于挖掘数字的数学特性，结合质因数分解与公式推导，考验算法设计与数学逻辑的结合能力。理解题目本质是解题的第一步，需明确“奇妙数字”的定义与计算规则。
二、解题思路
采用“质因数分解+数学公式推导”的双层策略：
1. 质因数分解：通过优化筛法（仅处理奇数+特判2）高效分解输入数字 n 的质因数，存储为键值对（质因数/指数）。
2. 数学公式计算：对每个质因数指数 e，利用公式 k = floor((sqrt(8e + 1) - 1) / 2) 计算“奇妙子序列”数量，累加得到最终结果。 核心洞察：将数字特性转化为质因数指数的数学映射，避免暴力枚举，大幅提升时间复杂度。
三、解题步骤
1. 输入与预处理：禁用流同步加速输入，读取 n。
2. 质因数分解函数 factorize(n)：
1.特判 n=1 直接返回空映射。
2.优先处理质因数2（偶数情况），减少后续循环次数。
3.奇数筛法：从3开始，步长2遍历，避免重复计算偶数。
4.最终剩余质因数（若 n 为大于2的质数）单独处理。
3. 求解函数 solve(n)：
1.调用 factorize 获取质因数映射。
2.遍历每个质因数 p 与指数 e，代入公式计算 k 并累加。
4. 输出结果：直接输出 solve(n) 值。
四、代码与注释
#include <iostream>
#include <unordered_map>
#include <cmath>
using namespace std;
// 质因数分解函数
unordered_map<int, int> factorize(long long n) {
unordered_map<int, int> factors;
if (n == 1) return factors; // 特判1（无质因数）
while (n % 2 == 0) factors[2]++, n /= 2; // 优先处理质因数2
for (int i = 3; i <= sqrt(n); i += 2) { // 仅遍历奇数质因数
while (n % i == 0) factors[i]++, n /= i;
}
if (n > 2) factors[n]++; // 剩余质因数（若n为质数）
return factors;
}
int solve(long long n) {
if (n == 1) return 0;
auto factors = factorize(n);
int res = 0;
for (auto [p, e] : factors) {
int k = floor((sqrt(8 * e + 1) - 1) / 2); // 核心公式计算奇妙序列数
res += k;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
cout << solve(n);
return 0;
}五、总结
本文通过解析GESP五级「奇妙数字」题目与用户代码，揭示了算法竞赛中“数学建模+高效实现”的重要性。代码巧妙结合质因数分解与推导公式，在时间复杂度与代码简洁性上达到平衡。学习此类题目可培养将数学思维融入编程的能力，建议读者深入理解质因数分解优化技巧与公式推导逻辑，提升竞赛解题水平。
原创内容 转载请注明出处
