「Luogu P2303」「SDOI2012」Longge的问题

Descrption

给定一个正整数 $n\ (0 < n \leq 2^{32})$，求 $\sum\limits_{i=1}^{n}\gcd(i,n)$ 。

Source

[Luogu]P2303

Solution

前置知识：

常见积性函数 - 欧拉函数 - 求一个数的欧拉函数值

假设 $\gcd(i,n) = d\ (1 \leq i \leq n) $，则 $\gcd(\frac{i}{d},\frac{n}{d}) = 1$ 。

因为 $d \mid n$，所以 $d$ 一定是 $n$ 的因数。对于某一个 $d$，我们设 $i = d \times x\ (\frac{1}{d} \leq x \leq \frac{n}{d})$，则

$$\gcd(\frac{i}{d},\frac{n}{d}) = \gcd(x,\frac{n}{d}) = 1$$

有多少个符合条件的 $x$ 与 $\frac{n}{d}$ 互质呢？显然有 $\varphi(\frac{n}{d})$ 个。而 $d$ 是一个定值，所以也同样有 $\varphi(\frac{n}{d})$ 个 $i$ 满足 $\gcd(i,n) = d$，这个 $d$ 所产生的贡献即为 $\varphi(\frac{n}{d}) \times d$ 。枚举每一个因数 $d$，把它们的贡献加起来就能得到答案，即

$$\sum\limits_{d \mid n} \left[ \varphi \left(\frac{n}{d} \right) \times d \right]$$

枚举因数 $d$，只需要 $O(\sqrt n)$ 的时间复杂度。$n$ 最大为 $2^{32}$，肯定不能 $O(n)$ 预处理出 $\varphi(1) \sim \varphi(n)$，所以可以用 $O(\sqrt n)$ 的时间复杂度求出一个数的欧拉函数值。总时间复杂度为 $O(n\ 的因数个数 \times \sqrt n)$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

inline LL getPhi(LL n) {
    LL res = n;
    for (LL i = 2; i * i <= n; ++i)
        if (n % i == 0) {
            res -= res / i;
            for (; n % i == 0; n /= i);
        }
    if (n > 1) res -= res / n;
    return res;
}//求一个数的欧拉函数值 

LL ans, n;

int main() {
    read(n);
    for (LL i = 1; i * i <= n; ++i)//枚举 n 的约数 d
        if (n % i == 0) {
            LL d1 = i, d2 = n / i;//得到因数 i 和 n / i 
            ans += d1 * getPhi(n / d1);
            if (d1 != d2) ans += d2 * getPhi(n / d2);//d1 = d2 时只能加一次答案 
        }
    write(ans);
    putchar('\n');
    return 0;
}