原题目链接：Link。
虽然已经被 A 穿了但还是写一下。
\[\sum_{i = 1}^n \gcd(i, n) = \sum_{d \vert n} \sum_{i = 1}^n [\gcd(i, n) = d] \]这一步显然，因为 \(\forall \gcd(i, n)\) 必定为 \(n\) 的因数，所以可以枚举因数 \(d\)。
\[\sum_{d \vert n} \sum_{i = 1}^n [\gcd(i, n) = d] = \sum_{d \vert n} \sum_{i = 1}^n [\gcd(\frac{i}{d}, \frac{n}{d}) = 1] \]因为 \(\gcd(i, n) = d\)，显然 \(d \mid i\)，又 \(d \mid n\)，所以可以直接运用 \(\gcd(ac , bc) = cd \Longleftrightarrow \gcd(a, b) = d\)，同时除掉 \(d\)。
\[\sum_{d \vert n} \sum_{i = 1}^n [\gcd(\frac{i}{d}, \frac{n}{d}) = 1] = \sum_{d \vert n} \sum_{i = 1}^{\frac{n}{d}} [\gcd(i, \frac{n}{d}) = 1] \]上文说到 \(d \mid i\)，所以 \(i\) 只能是 \(d\) 的倍数，\(i \in \{d, 2d, \cdots, \frac{n}{d}d \}\)，共有 \(\frac{n}{d}\) 个。这些数除掉 \(d\) 的结果就为 \(\{1, 2, \cdots, \frac{n}{d} \}\)。所以可以直接循环到 \(\frac{n}{d}\)，并且把 \(\gcd(\frac{i}{d}, \frac{n}{d})\) 换成 \(\gcd(i, \frac{n}{d})\)。
\[\sum_{d \vert n} \sum_{i = 1}^{\frac{n}{d}} [\gcd(i, \frac{n}{d}) = 1] = \sum_{d \vert n} \varphi(\frac{n}{d}) \]只看右边，\(\sum_{i = 1}^{\frac{n}{d}} [\gcd(i, \frac{n}{d}) = 1]\)，互质出来了！！！这就等于欧拉函数，也就是 \(\varphi(\frac{n}{d})\)。
然后你就发现可以做了。预先筛出质数，每次暴力除质数求欧拉函数即可。
#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 16) + 5;
#define int long long
int n, prime[N], tot;
bool v[N];
void euler(int n) {
for (int i = 2; i * i <= n; i++) { // 筛到根号就可以
if (!v[i]) prime[++tot] = i;
for (int j = 1; j <= tot && i * prime[j] <= n; j++) {
v[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
} // 线性筛
int phi(int n) {
int ans = n;
for (int i = 1; i <= tot; i++)
if (n % prime[i] == 0) {
ans = ans / prime[i] * (prime[i] - 1);
while (n % prime[i] == 0) n /= prime[i];
} // 这里把暴力试除换成了除质数
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
signed main() {
cin >> n;
euler(n);
int sum = 0;
for (int i = 1; i * i <= n; i++)
if (n % i == 0) {
sum += i * phi(n / i); // i 是 n 的因数，n / i 也是，要特判完全平方数的情况
// 枚举的复杂度 O(n) -> O(sqrt(n))
if (i * i != n) sum += n / i * phi(i);
}
cout << sum << endl;
return 0;
}
当然也可以每次暴力试除求欧拉函数，还 faster（？）
随便贴一个：
#include <cstdio>
long long phi(long long n) {
long long res = n;
for(long long i = 2; i * i <= n; i++) {
if(n % i == 0) res = res / i * (i - 1);
while(n % i == 0) n /= i;
}
if(n > 1) res = res / n * (n - 1);
return res;
}
long long f(long long x) {
long long res = 0LL, i = 1LL;
for(; i * i < x; i++)
if(x % i == 0) res += i * phi(x / i) + (x / i) * phi(i);
if(i * i == x) res += i * phi(i);
return res;
}
int main() {
long long n;
scanf("%lld", &n);
printf("%lld", f(n));
return 0;
}