质因数分解与三角数公式：2024 GESP五级奇妙数字问题详解

一、问题理解与数学基础

奇妙数字问题要求我们找到一个数字n的"奇妙值"，这个值实际上是n的质因数分解中，各质因数的指数所能构成的最大三角数之和。三角数是指可以排列成等边三角形的数字，公式为k(k+1)/2。

二、完整代码实现（带详细注释）

#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;
    
    // 处理奇数因子，从3开始，每次加2
    for (int i = 3; i <= sqrt(n); i += 2)
        while (n % i == 0) factors[i]++, n /= i;
    
    // 处理剩余的大于2的质数
    if (n > 2) factors[n]++;
    return factors;
}

// 计算奇妙值的核心函数
int solve(long long n) {
    if (n == 1) return 0;  // 1的奇妙值为0
    auto factors = factorize(n);  // 获取质因数分解
    int res = 0;  // 初始化结果
    
    // 对每个质因数及其指数进行处理
    for (auto [p, e] : factors) {
        // 计算该指数能构成的最大三角数k
        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;
}

三、算法核心解析

1. 质因数分解：

• 首先处理偶数因子(2)

• 然后检查奇数因子(3,5,7...)

• 最后处理剩余的大质数

2. 三角数计算：

• 使用公式k=⌊(√(8e+1)-1)/2⌋

• 该公式是解方程k(k+1)/2 ≤ e的最大整数k

3. 时间复杂度：

• 质因数分解：O(√n)

• 三角数计算：O(1)每质因数

• 总复杂度：O(√n)

四、数学原理详解

1. 三角数性质：

• 三角数序列：1,3,6,10,15,...

• 通项公式：Tₖ = k(k+1)/2

2. 逆向求解k：

• 从不等式k(k+1)/2 ≤ e

• 推导出二次方程k² + k - 2e ≤ 0

• 应用求根公式得到k的最大整数值

五、优化与扩展

1. 预计算优化：

• 可以预先计算常见质数

• 使用筛法预处理小质数

2. 大数处理：

• 对于极大数(n>1e18)

• 可考虑Pollard's Rho算法

3. 实际问题应用：

• 类似原理可用于组合数学

• 资源分配问题中也有应用