「最大公因数和」题解

问题分析

计算 $\sum_{i=1}^n \gcd(i, n)$，其中 $n$ 最大可达 $2^{32}-1$，需要高效的数学方法。

核心思路

利用数论变换和欧拉函数性质，将问题转化为对 $n$ 的所有约数求和。

关键公式推导

设 $d = \gcd(i, n)$，则：

• $d \mid n$
• $\gcd\left(\frac{i}{d}, \frac{n}{d}\right) = 1$

因此：

$$\sum_{i=1}^n \gcd(i, n) = \sum_{d \mid n} d \cdot \varphi\left(\frac{n}{d}\right) $$

其中 $\varphi$ 是欧拉函数。

算法详解

1. 欧拉函数计算

int phi(int n) {
    int ans = n;
    // 质因数分解
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1);  // φ(n) = n × ∏(1 - 1/p)
            while (n % i == 0)
                n /= i;  // 去除所有该质因子
        }
    }
    // 处理剩余的质因子
    if (n > 1)
        ans = ans / n * (n - 1);
    return ans;
}

欧拉函数性质：$\varphi(n) = n \times \prod_{p|n}(1 - \frac{1}{p})$

2. 主算法

int ans = 0;
// 枚举n的所有约数
for (int i = 1; i * i <= n; i++) {
    if (!(n % i)) {  // i是n的约数
        ans += phi(i) * (n / i);    // 对应约数d = n/i
        if (i * i != n)
            ans += phi(n / i) * i;  // 对应约数d = i
    }
}

算法逻辑：

• 对于每个约数 $d$，计算 $d \times \varphi(\frac{n}{d})$
• 通过对称性，同时处理 $d$ 和 $n/d$

算法正确性

公式验证

对于 $n = 6$，约数为 $1, 2, 3, 6$：

• $d=1$: $1 \times \varphi(6) = 1 \times 2 = 2$
• $d=2$: $2 \times \varphi(3) = 2 \times 2 = 4$
• $d=3$: $3 \times \varphi(2) = 3 \times 1 = 3$
• $d=6$: $6 \times \varphi(1) = 6 \times 1 = 6$

总和：$2 + 4 + 3 + 6 = 15$ ✓

等价形式

原公式也可写为：

$$\sum_{i=1}^n \gcd(i, n) = \sum_{d \mid n} \frac{n}{d} \cdot \varphi(d) $$

代码中实际使用的是这种形式。

复杂度分析

• 欧拉函数：$O(\sqrt{n})$，最坏情况 $n$ 为质数
• 约数枚举：$O(\sqrt{n})$，只枚举到 $\sqrt{n}$
• 总复杂度：$O(\text{约数个数} \times \sqrt{n})$

对于 $n < 2^{32}$，约数个数通常很少，算法效率很高。

样例验证

样例：$n = 6$

• 约数：$1, 2, 3, 6$
• $\varphi(1)=1, \varphi(2)=1, \varphi(3)=2, \varphi(6)=2$
• 计算：$1\times6 + 1\times3 + 2\times2 + 2\times1 = 6+3+4+2=15$

关键技巧

1. 数论变换：将求和转化为约数求和
2. 对称枚举：只枚举到 $\sqrt{n}$，利用对称性
3. 欧拉函数：利用质因数分解高效计算
4. 整数溢出防护：使用 long long

总结

本题的巧妙之处在于：

1. 问题转化：将看似复杂的求和转化为数论问题
2. 欧拉函数应用：利用 $\varphi$ 函数计数互质整数对
3. 高效实现：通过数学性质避免暴力计算
4. 边界处理：正确处理平方数情况

这种"数学推导 + 高效实现"的方法在解决数论问题时非常有效。