当前位置：首页 > GESP > 2024 GESP五级「奇妙数字」深度解析：高效解题代码与数学逻辑揭秘(洛谷B4070)

2024 GESP五级「奇妙数字」深度解析：高效解题代码与数学逻辑揭秘(洛谷B4070)

6个月前 (06-06)

一、题目解读

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