「Longge's problem」龙哥的问题

形式化题目

给定正整数 $N$ ，求 $\sum_{i=1}^{N} \gcd(i, N)$ 。

正解

思路

1. 按 gcd 取值分组

\sum_{i=1}^{N}\gcd(i,N)=\sum_{d\mid N} d\cdot\#\{i:\gcd(i,N)=d\}=\sum_{d\mid N} d\cdot\varphi(N/d)

把 $\gcd = d$ 的 $i$ 归为一组： $\gcd(i,N)=d \iff \gcd(i/d, N/d)=1$ ，恰好 $\varphi(N/d)$ 个。

2. 积性 + 局部因子

$f(N)=\sum_{d\mid N} d\,\varphi(N/d)$ 是积性函数（ $d$ 与 $\varphi$ 的狄利克雷卷积）。只需算质因子幂 $N=p^a$ 处的值：

f(p^a)=\sum_{k=0}^{a} p^{k}\varphi(p^{a-k}) = p^{a-1}\bigl(p + a(p-1)\bigr)

（展开 $\varphi(p^{a-k})=p^{a-k-1}(p-1)$ 等比求和即得。）

于是对 $N=\prod p_i^{a_i}$ ：

f(N)=\prod_i p_i^{a_i-1}\bigl(p_i + a_i(p_i - 1)\bigr)

$O(\sqrt N)$ 完成质因数分解，连乘即得答案。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 17:00
# update_at: 2026-10-01 17:00

import sys
from collections.abc import Iterator


def prime_powers(n: int) -> Iterator[tuple[int, int]]:
    """把 n 分解质因数，依次产出 (质因子 p, 指数 a)，即 n = ∏ p^a。"""
    p = 2
    while p * p <= n:
        if n % p == 0:
            a = 0
            while n % p == 0:
                n //= p
                a += 1
            yield p, a
        p += 1
    if n > 1:  # 除完所有 ≤ √n 的因子后还剩的大于 1 的部分必然是质数
        yield n, 1


def answer(n: int) -> int:
    """求 ∑_{1 ≤ i ≤ n} gcd(i, n)：答案关于 n 是积性的，在每个质因子幂上乘一个局部因子。"""
    total = 1
    for p, a in prime_powers(n):
        total *= p ** (a - 1) * (p + a * (p - 1))
    return total


def solve() -> None:
    n = int(sys.stdin.buffer.read())  # 输入只有一个整数 N
    print(answer(n))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 16:50
 * update_at: 2026-10-04 22:12
 */
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;

// 返回 f(N) = sum_{i=1}^{N} gcd(i,N)
// 利用积性：f = id * phi，对质因子幂 p^a，局部因子为 p^{a-1} * (p + a*(p-1))
ll solve(ll N) {
    ll ans = 1;
    // 试除法分解质因数，O(sqrt(N))
    for (ll p = 2; p * p <= N; ++p) {
        if (N % p == 0) {
            ll a = 0;
            ll pw = 1; // p^a
            while (N % p == 0) {
                N /= p;
                ++a;
                pw *= p;
            }
            // 局部因子：p^{a-1} * (p + a*(p-1))
            // pw 已经是 p^a，所以 p^{a-1} = pw / p
            ll part = (pw / p) * (p + a * (p - 1));
            ans *= part;
        }
    }
    // 剩余一个大于 sqrt(原N) 的质因子
    if (N > 1) {
        // 此时 a = 1, p = N, p^{a-1} = 1, 局部因子 = 1 * (N + 1*(N-1)) = 2*N - 1
        ll part = 2 * N - 1;
        ans *= part;
    }
    return ans;
}

int main() {
    ll N;
    scanf("%lld", &N);
    printf("%lld\n", solve(N));
    return 0;
}

复杂度

时间复杂度： $O(\sqrt N)$ 。
空间复杂度： $O(1)$ 。

总结

「gcd 之和」类问题的标准变形：按 $\gcd$ 取值分组，化为 $\sum_{d\mid N} d\,\varphi(N/d)$ 。
记住 $f = \mathrm{id} * \varphi$ 是积性函数，质因子幂上的局部因子 $p^{a-1}(p+a(p-1))$ 可直接套用。
单个 $N$ 时无需线性筛， $O(\sqrt N)$ 试除分解质因数即可。

「Longge's problem」 龙哥的问题

目录

形式化题目

正解

思路

1. 按 gcd 取值分组

2. 积性 + 局部因子

代码

复杂度

总结

「Longge's problem」龙哥的问题