算法
(欧拉函数) $O(\text{因子个数}\cdot \sqrt{n})$
枚举 $gcd$:
$$\begin{array}{l} \sum\limits_{i = 1}^n {\gcd \left( {i,n} \right)} = \sum\limits_{\left. d \right|n} {d\sum\limits_{i = 1}^n {\left[ {\gcd \left( {i,n} \right) = d} \right]} } \\ = \sum\limits_{\left. d \right|n} {d\sum\limits_{i = 1}^{\frac{n}{d}} {\left[ {\gcd \left( {i,\frac{n}{d}} \right) = 1} \right]} } \\ = \sum\limits_{\left. d \right|n} {d\varphi \left( {\frac{n}{d}} \right)} \\ \end{array} $$
枚举 $n$ 的约数直接求。
坑点:$2^{32}$ 会爆int
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
ll get_euler(ll a) {
ll res = a;
for (ll i = 2; i * i <= a; ++i) {
if (a % i == 0) {
res = res / i * (i - 1);
while (a % i == 0) a /= i;
}
}
if (a > 1) res = res / a * (a - 1);
return res;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
ll n;
cin >> n;
ll res = 0;
for (ll i = 1; i * i <= n; ++i) {
if (n % i == 0) {
res += i * get_euler(n / i);
if (i != n / i) res += n / i * get_euler(i);
}
}
cout << res << '\n';
return 0;
}