1. 题目背景与核心挑战
UVa 13279 "Divisors" 是ICPC/ACM竞赛中的一道经典数论题目，主要考察选手对因数计算和数论优化的掌握程度。题目要求：给定一个正整数N，计算其所有因数的立方和。即求：
[ \sigma_3(N) = \sum_{d|N} d^3 ]
这道题的难点在于：
- 直接暴力计算在N较大时（如1e12）会超时
- 需要掌握数论中因数函数的积性性质
- 要求对质因数分解和模运算有深入理解
2. 数学原理与算法选择
2.1 因数立方和的积性性质
关键发现：σ₃(n)是一个积性函数。这意味着如果n可以分解为互质的两个数a和b（即gcd(a,b)=1），那么：
[ \sigma_3(ab) = \sigma_3(a) \times \sigma_3(b) ]
这个性质让我们可以将问题分解为对n的每个质因数幂次单独计算，最后将结果相乘。
2.2 质数幂次的计算公式
对于一个质数p的k次幂，其因数立方和可以直接用公式计算：
[ \sigma_3(p^k) = 1 + p^3 + p^6 + \cdots + p^{3k} = \frac{p^{3(k+1)} - 1}{p^3 - 1} ]
这个等比数列求和公式是解题的核心数学工具。
2.3 算法步骤分解
- 对N进行质因数分解：N = p₁^a₁ × p₂^a₂ × ... × pₘ^aₘ
- 对每个质因数pᵢ，计算σ₃(pᵢ^aᵢ)
- 将所有σ₃(pᵢ^aᵢ)相乘得到最终结果
3. 关键实现细节
3.1 高效的质因数分解
对于大数N（≤1e12），我们需要优化的质因数分解方法：
cpp复制vector<pair<long long, int>> factorize(long long n) {
vector<pair<long long, int>> factors;
// 处理2的因子
if (n % 2 == 0) {
int cnt = 0;
while (n % 2 == 0) {
n /= 2;
cnt++;
}
factors.emplace_back(2, cnt);
}
// 处理奇数因子
for (long long i = 3; i * i <= n; i += 2) {
if (n % i == 0) {
int cnt = 0;
while (n % i == 0) {
n /= i;
cnt++;
}
factors.emplace_back(i, cnt);
}
}
// 处理剩余的大质数
if (n > 1) {
factors.emplace_back(n, 1);
}
return factors;
}
3.2 等比数列求和的高效计算
计算σ₃(p^k) = (p^(3(k+1)) - 1)/(p^3 - 1)时需要注意：
- 使用快速幂算法计算大数次方
- 处理除法时需要模逆元（如果题目要求取模）
快速幂实现示例：
cpp复制long long pow_mod(long long base, long long exp, long long mod) {
long long result = 1;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp /= 2;
}
return result;
}
3.3 模运算处理
如果题目要求结果取模（常见于编程竞赛），需要注意：
- 除法要转换为乘以模逆元
- 使用费马小定理计算模逆元（当模为质数时）
模逆元计算：
cpp复制long long inv(long long a, long long mod) {
return pow_mod(a, mod - 2, mod);
}
4. 完整解决方案代码
结合上述分析，完整的C++解决方案如下：
cpp复制#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
vector<pair<ll, int>> factorize(ll n) {
vector<pair<ll, int>> factors;
if (n % 2 == 0) {
int cnt = 0;
while (n % 2 == 0) {
n /= 2;
cnt++;
}
factors.emplace_back(2, cnt);
}
for (ll i = 3; i * i <= n; i += 2) {
if (n % i == 0) {
int cnt = 0;
while (n % i == 0) {
n /= i;
cnt++;
}
factors.emplace_back(i, cnt);
}
}
if (n > 1) {
factors.emplace_back(n, 1);
}
return factors;
}
ll pow_mod(ll base, ll exp, ll mod) {
ll result = 1;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp /= 2;
}
return result;
}
ll inv(ll a, ll mod) {
return pow_mod(a, mod - 2, mod);
}
ll sigma3(ll p, int k, ll mod) {
ll p3 = pow_mod(p, 3, mod);
ll numerator = (pow_mod(p3, k + 1, mod) - 1 + mod) % mod;
ll denominator = (p3 - 1 + mod) % mod;
return numerator * inv(denominator, mod) % mod;
}
ll solve(ll n, ll mod) {
if (n == 0) return 0;
if (n == 1) return 1;
auto factors = factorize(n);
ll result = 1;
for (auto [p, k] : factors) {
result = result * sigma3(p, k, mod) % mod;
}
return result;
}
int main() {
ll n, mod = 1000000007; // 假设模数为1e9+7
while (cin >> n) {
cout << solve(n, mod) << endl;
}
return 0;
}
5. 性能优化与边界情况
5.1 算法复杂度分析
- 质因数分解部分：O(√n) 最坏情况
- 快速幂部分：O(log k) 每个质因数
- 总体复杂度：O(√n + log k)
对于n≤1e12，这个复杂度是可以接受的。
5.2 特殊情况的处理
- n=0：根据题目要求处理（通常返回0）
- n=1：唯一因数是1，返回1
- 大质数：当n本身是质数时，σ₃(n) = 1 + n³
5.3 进一步优化思路
- 预计算小质数：使用筛法预计算小质数可以加速分解
- Pollard's Rho算法：对于极大数（>1e18）的质因数分解
- 记忆化：如果多次查询，可以缓存已计算的质因数分解结果
6. 竞赛中的实战技巧
6.1 常见错误与调试
- 整数溢出：确保使用足够大的数据类型（long long）
- 模运算错误：注意负数取模要先加mod再取模
- 边界条件：特别测试n=0,1,质数等情况
6.2 测试用例设计
建议测试以下情况：
- 小质数：如7 → 1 + 343 = 344
- 质数的幂：如8=2³ → 1 + 8 + 64 + 512 = 585
- 平方数：如36=2²×3² → σ₃(2²)×σ₃(3²)
- 大质数：如999983（已知质数）
6.3 时间与空间权衡
- 空间换时间：预计算小质数表
- 快速幂vs预计算：根据问题规模选择
- 输入规模：根据题目约束选择合适算法
7. 数学理论延伸
7.1 一般化的因数函数
σ₃(n)是更一般的因数函数σₖ(n)的特例（k=3）：
[ \sigma_k(n) = \sum_{d|n} d^k ]
所有σₖ(n)都是积性函数，具有类似的性质。
7.2 数论函数的Dirichlet卷积
因数函数可以通过除数函数的Dirichlet卷积来表示，这是更高级的数论工具。
7.3 模形式与解析数论
在更高级的数学中，这类函数与模形式和L函数有深刻联系，是解析数论的研究对象。
8. 变种问题与扩展思考
8.1 问题变种
- 计算因数平方和（σ₂）
- 计算因数个数（σ₀）
- 计算因数和（σ₁）
- 计算奇数因数的立方和
8.2 扩展挑战
- 多个查询：给定Q个查询，每个查询给出一个n，求σ₃(n)
- 区间查询：给定L,R，求σ₃(L)+σ₃(L+1)+...+σ₃(R)
- 在线查询：处理动态更新的n值
8.3 实际应用
虽然看似理论，但这类函数在密码学（如RSA）、编码理论等领域有实际应用。