[SDOI2012] Longge 的问题

标签: #数论 #欧拉函数
原题目: luogu-P2303
简要描述: 欧拉函数入门(模板)题目

1 题目简述

题目：给定整数 nn (1≤n<2321 \le n < 2^{32})，求 ∑i=1ngcd⁡(i,n)\sum_{i=1}^n \gcd(i, n)。 核心难点：数据范围非常大，普通的 O(n)O(n) 遍历做法会超时（TLE），需要推导出一个与 nn 的因子相关的更高效公式。

2 思路推导

暴力法的局限

最直接的思路是枚举 ii 从 11 到 nn，计算 gcd⁡(i,n)\gcd(i, n) 并累加。 然而，题目中 nn 高达 2322^{32}（约 42 亿）。计算机 1 秒大概能处理 10810^8 级别的数据，暴力法显然行不通。我们需要寻找 O(n)O(\sqrt{n}) 甚至更优的解法。

转换视角：枚举 GCD

我们可以不枚举 ii，而是枚举 gcd⁡(i,n)\gcd(i, n) 的值。 设 g=gcd⁡(i,n)g = \gcd(i, n)。显然，gg 必须是 nn 的因子。 如果我们能算出对于每一个因子 dd，有多少个 ii 满足 gcd⁡(i,n)=d\gcd(i, n) = d，那么总和就可以写成：

Ans=∑d∣nd×count(i∈[1,n]∣gcd⁡(i,n)=d)\text{Ans} = \sum_{d|n} d \times \text{count}(i \in [1, n] \mid \gcd(i, n) = d)

这里还是构造法,或者叫贡献法,反过来找集合中的元素

利用欧拉函数 (ϕ\phi)

如何求满足 gcd⁡(i,n)=d\gcd(i, n) = d 的 ii 的个数？

  1. 既然 gcd⁡(i,n)=d\gcd(i, n) = d，那么 ii 一定是 dd 的倍数。设 i=k×di = k \times d。
  2. 代入原式：gcd⁡(k×d,n)=d\gcd(k \times d, n) = d。
  3. 两边同除以 dd，得到：gcd⁡(k,n/d)=1\gcd(k, n/d) = 1。
  4. 因为 1≤i≤n1 \le i \le n，所以 1≤k×d≤n1 \le k \times d \le n，即 1≤k≤n/d1 \le k \le n/d。

结论：满足条件的 ii 的个数，等价于在区间 [1,n/d][1, n/d] 中与 n/dn/d 互质的数的个数。 根据定义，这就是欧拉函数 ϕ(n/d)\phi(n/d)。

最终公式

我们将计数部分代回原公式，得到：

Ans=∑d∣nd×ϕ(nd)\text{Ans} = \sum_{d|n} d \times \phi(\frac{n}{d})

3 算法实现

由于 nn 很大，我们不能用线性筛预处理欧拉函数。我们需要采用 “枚举因子 + 单独计算 ϕ\phi” 的策略：

  1. 枚举因子：遍历 ii 从 11 到 n\sqrt{n}。如果 i∣ni|n，则 ii 和 n/in/i 都是因子。
  2. 计算 ϕ(x)\phi(x)：对于每个因子，利用分解质因数的方法在 O(x)O(\sqrt{x}) 时间内算出欧拉函数值。

复杂度分析

  • 外层枚举因子：O(n)O(\sqrt{n})。
  • 内层计算 ϕ\phi：最坏情况 O(n)O(\sqrt{n})，但实际上因子的数值通常小于 nn，且计算非常快。
  • 总体能够轻松通过 2322^{32} 的数据限制。

4 C++ 代码参考

python
copy 
        
1
2
3

        >>> (2**32) *4 / 1024/1024
16384.0

上面的这个计算告诉我们,如果我们使用线性的 欧拉筛, 会超过内存

cpp
copy 
        
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

        /**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * date: 2025-12-17 17:10:30
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 1e7+5;
int n,m;
ll ans;


int phi[maxn]; // 欧拉函数
bool st[maxn]; // st[i] = 1 表示被删除,不是素数
std::vector<int> primes; //存素数

void get_phi_line(){
    phi[1] = 1;
    for(int i = 2;i <= n ;++i ) // i: 2->n
    {

        if( !st[i])
        {
            primes.push_back(i);
            phi[i] = i - 1;
        }

        //枚举前面的素数
        for(auto p : primes) {

            if( i * p > n) break;
            st[i * p ] = 1;

            if( i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            }
            else {
                phi[p * i] = phi[i] * (p-1); 
            }

        }
    }
}


signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    std::cin >> n;

    get_phi_line();

    for(ll i = 1 ;i*i <= n; i++) {
        if( n % i == 0) {
            // i 是d的因子
            ans += i * phi[n/i];

            // 不能重复的计算
            if( i *i != n) {
                ans += (n /i) * phi[i];
            }
        }
    }

    std::cout << ans << "\n";
    
    return 0;
}

直接使用欧拉函数

cpp
copy 
        
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
49
50
51
52
53
54
55
56
57
58
59

        /**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * date: 2025-12-17 17:10:30
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

ll n,m;
ll ans;

ll get_phi(ll n) {
    ll res = n;

    // 求所有的因子
    for(ll i = 2;i * i <= n ; ++i)
    {
        if( n % i == 0) {

            // 公式：res = res * (1 - 1/p) => res = res / p * (p - 1)  
            res = res / i *(i-1);


            //去除质因子
            while( n % i == 0) n /= i;
        }

    }
    // 处理剩余的大质数因子
    if( n > 1) res = res / n * (n-1);

    return res;
}



signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    std::cin >> n;


    for(ll i = 1 ;i*i <= n; i++) {
        if( n % i == 0) {
            // i 是d的因子
            ans += i * get_phi(n/i);

            // 不能重复的计算
            if( i *i != n) {
                ans += (n /i) * get_phi(i);
            }
        }
    }

    std::cout << ans << "\n";
    
    return 0;
}
cpp
copy 
        
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

        #include <iostream>

using namespace std;

typedef long long ll;

// 单独求解欧拉函数：O(sqrt(x))
ll get_phi(ll x) {
    ll res = x;
    for (ll i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            // 公式：res = res * (1 - 1/p) => res = res / p * (p - 1)
            res = res / i * (i - 1);
            while (x % i == 0) x /= i; // 除尽质因子
        }
    }
    if (x > 1) res = res / x * (x - 1); // 处理剩余的大质因子
    return res;
}

int main() {
    // 优化 I/O 速度
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n;
    while (cin >> n) { // 注意题目可能包含多组数据或单组数据，视具体评测环境而定
        ll ans = 0;
        
        // 枚举因子：O(sqrt(n))
        for (ll i = 1; i * i <= n; ++i) {
            if (n % i == 0) {
                // 处理因子 d = i
                // 对应项：i * phi(n/i)
                ans += i * get_phi(n / i);
                
                // 处理因子 d = n/i (避免完全平方数重复计算)
                if (i * i != n) {
                    // 对应项：(n/i) * phi(i)
                    ans += (n / i) * get_phi(i);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}