题解：热气球数学家的牺牲决策

题意分析

这是一个有趣的数学问题，描述$10$位数学家需要通过数学方法公平地决定谁要牺牲。具体规则如下：

1. 每人提供一个整数$a_i$（$1 \leq a_i \leq 10000$）
2. 计算所有数乘积$N$的正约数个数
3. 根据这个数个位数字决定牺牲者

解题思路

1. 约数个数的计算：利用数论知识，一个数的正约数个数可以通过其质因数分解求得。若$N = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}$，则其约数个数为$(e_1+1)(e_2+1)\cdots(e_k+1)$
2. 个位数计算：只需要计算约数个数的个位数，不需要计算完整数值
3. 模运算性质：利用$(a \times b) \mod 10 = [(a \mod 10) \times (b \mod 10)] \mod 10$简化计算

实现步骤

1. 输入处理：读取10个整数
2. 质因数分解：对每个数进行质因数分解
3. 合并质因数：统计所有质因数的总指数
4. 计算约数个数：应用公式计算约数个数
5. 求个位数：输出约数个数的个位数字

代码注释

#include <iostream>
#include <vector>
#include <map>
#include <cmath>  // 用于sqrt函数

using namespace std;

// 质因数分解函数
// 参数：整数x
// 返回值：map，键为质因数，值为对应指数
map<int, int> prime_factorization(int x) {
    map<int, int> factors;  // 存储质因数分解结果
    
    // 从2开始试除，直到i*i超过x
    for (int i = 2; i * i <= x; ++i) {
        // 当i是x的因数时，不断除尽i
        while (x % i == 0) {
            factors[i]++;  // 对应质因数的指数加1
            x /= i;        // 除掉一个i因子
        }
    }
    
    // 处理剩余的大于sqrt(x)的质因数
    if (x > 1) {
        factors[x]++;  // x本身就是一个质数
    }
    
    return factors;
}

int main() {
    vector<int> a(10);          // 存储10个输入数
    map<int, int> total_factors; // 存储所有质因数的总指数
    
    // 读取输入数据
    for (int i = 0; i < 10; ++i) {
        cin >> a[i];  // 读取第i个数
        
        // 对当前数进行质因数分解
        map<int, int> factors = prime_factorization(a[i]);
        
        // 将当前数的质因数合并到总表中
        for (auto &[prime, cnt] : factors) {
            total_factors[prime] += cnt;  // 累加相同质因数的指数
        }
    }
    
    // 计算约数个数N = ∏(e_i + 1)
    long long N = 1;  // 使用long long防止溢出
    for (auto &[prime, cnt] : total_factors) {
        N *= (cnt + 1);  // 应用约数个数公式
    }
    
    // 输出N的个位数字
    cout << N % 10 << endl;
    
    return 0;  // 程序正常结束
}

复杂度分析

1. 时间复杂度：
   • 质因数分解：最坏情况$O(\sqrt{n})$，10个数总时间$O(10 \times \sqrt{10000}) = O(1000)$
   • 合并质因数和计算约数个数：$O(k)$，k为不同质因数个数
2. 空间复杂度：
   • 存储质因数分解结果：$O(k)$