题目解析：计算∑gcd(i, N) (1≤i≤N)

问题描述

给定一个正整数N（1 < N < 2³¹），要求计算从1到N所有整数i与N的最大公约数（gcd）之和，即∑gcd(i, N)。

解题思路

1. 数学推导：

   • 对于每个可能的d（d是N的约数），统计gcd(i, N) = d的i的个数。
   • 这个个数等于欧拉函数φ(N/d)，即小于等于N/d且与N/d互质的数的个数。
   • 因此总和可以表示为∑(d × φ(N/d))，其中d遍历N的所有约数。

2. 算法步骤：

   • 分解N的所有约数d。
   • 对每个约数d，计算φ(N/d)。
   • 累加所有d × φ(N/d)的值。

关键步骤说明

1. 欧拉函数计算（phi函数）：

   • 初始化结果为n。
   • 通过试除法分解质因数，对每个质因数p，按公式result -= result / p调整结果。
   • 最后处理可能剩余的大于sqrt(n)的质因数。

2. 约数遍历与求和：

   • 遍历1到$sqrt(N)$的所有整数d，检查是否为N的约数。
   • 对每个约数d，计算其贡献$d × φ(N/d)$。
   • 同时处理对应的另一个约数$N/d（当d ≠ N/d时）$。

3. 输入输出处理：

   • 使用scanf高效读取输入（适用于大规模数据）。
   • 使用printf输出结果。

复杂度分析

• 时间复杂度：主要取决于欧拉函数的计算，最坏情况下为$O(√N)$。
• 空间复杂度：$O(1)$，仅使用常数空间。

示例分析

输入1：

2

处理过程：

• 约数d=1：φ(2/1)=φ(2)=1 → 贡献=1×1=1
• 约数d=2：φ(2/2)=φ(1)=1 → 贡献=2×1=2
• 总和=1+2=3

输出1：

3

输入2：

6

处理过程：

• 约数d=1：φ(6)=2 → 贡献=1×2=2
• 约数d=2：φ(3)=2 → 贡献=2×2=4
• 约数d=3：φ(2)=1 → 贡献=3×1=3
• 约数d=6：φ(1)=1 → 贡献=6×1=6
• 总和=2+4+3+6=15

输出2：

15

标程

#include <cstdio>
#include <cmath>

using namespace std;

typedef long long LL;  // 使用long long类型处理大数

// 计算欧拉函数φ(n)：小于等于n且与n互质的数的个数
LL phi(LL n) {
    LL result = n;
    // 分解质因数
    for (LL p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) {
                n /= p;  // 去除所有p因子
            }
            result -= result / p;  // 根据欧拉函数公式计算
        }
    }
    // 处理剩余的质因数（如果n>1）
    if (n > 1) {
        result -= result / n;
    }
    return result;
}

int main() {
    LL N;
    while (scanf("%lld", &N) != EOF) {  // 处理多组输入
        LL sum = 0;
        // 遍历所有可能的约数d（只需遍历到sqrt(N)）
        for (LL d = 1; d * d <= N; ++d) {
            if (N % d == 0) {  // 如果d是N的约数
                // 计算d对应的贡献：d × φ(N/d)
                sum += d * phi(N / d);
                // 处理对应的另一个约数N/d（避免重复计算）
                if (d != N / d) {
                    sum += (N / d) * phi(d);
                }
            }
        }
        printf("%lld\n", sum);  // 输出结果
    }
    return 0;
}

总结

该算法通过数学推导将问题转化为欧拉函数的计算，利用约数分解和对称性优化，高效求解了∑gcd(i, N)。适用于大数范围（N < 2³¹），保证了正确性和效率。