[SDOI2012] Longge 的问题

1 题目简述

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

2 思路推导

暴力法的局限

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

转换视角：枚举 GCD

我们可以不枚举 $i$ ，而是枚举 $\gcd(i, n)$ 的值。设 $g = \gcd(i, n)$ 。显然， $g$ 必须是 $n$ 的因子。如果我们能算出对于每一个因子 $d$ ，有多少个 $i$ 满足 $\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$ 的 $i$ 的个数？

既然 $\gcd(i, n) = d$ ，那么 $i$ 一定是 $d$ 的倍数。设 $i = k \times d$ 。
代入原式： $\gcd(k \times d, n) = d$ 。
两边同除以 $d$ ，得到： $\gcd(k, n/d) = 1$ 。
因为 $1 \le i \le n$ ，所以 $1 \le k \times d \le n$ ，即 $1 \le k \le n/d$ 。

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

最终公式

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

\text{Ans} = \sum_{d|n} d \times \phi(\frac{n}{d})

3 算法实现

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

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

复杂度分析

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

4 C++ 代码参考

python

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

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

cpp

/**
 * Author by Rainboy blog: https://blog.roj.ac.cn 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

/**
 * Author by Rainboy blog: https://blog.roj.ac.cn 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

#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;
}