题目描述
求：
其中 n ≤ 10^5。
用到的知识
记 φ(k) 为欧拉函数，其表示小于等于 k 且与 k 互质的正整数个数。
结论
\[\sum_{d=1}^{n} d \cdot \left(2\sum_{k=1}^{\lfloor n/d \rfloor} \varphi(k)-1\right)
\]
推导逻辑
将数对 (i, j) 按最大公因数 d 分类：
令 i = d·x，j = d·y，则：
- gcd(x, y) = 1（x 和 y 互质）
- x, y ≤ floor(n/d)（floor 表示向下取整）
互质对 (x, y) 的个数计算
设 m = floor(n/d)，则互质对的个数为：
\[\sum_{d=1}^{n} d \cdot \left(2\sum_{k=1}^{\lfloor n/d \rfloor} \varphi(k)-1\right)
\]
注：φ(k) 是欧拉函数，∑ 表示求和符号。
贡献累加
每个数对 (x, y) 对应原数对 (i, j) 的贡献值为 d，将所有情况累加即可得到最终结果：
\[\sum_{d=1}^{n} d \cdot \left(2\sum_{k=1}^{\lfloor n/d \rfloor} \varphi(k)-1\right)
\]
算法实现
知道了结论，我们还需求出对应的欧拉函数 φ(k) 以及 φ(k) 的前缀和。我们可以用线性筛去求欧拉函数。
时间复杂度：O(n)（n ≤ 10^5），满足 1s 的限制。
代码实现（C++）
#include <iostream>
#include <vector>
using namespace std;const int N = 1e5 + 5;int phi[N];
long long phi_sum[N];
bool is_prime[N];
vector<int> primes;void init_phi(int n) {for (int i = 1; i <= n; i++) is_prime[i] = true;is_prime[1] = false;phi[1] = 1;for (int i = 2; i <= n; i++) {if (is_prime[i]) {primes.push_back(i);phi[i] = i - 1;}for (int p : primes) {if (i * p > n) break;is_prime[i * p] = false;if (i % p == 0) {phi[i * p] = phi[i] * p;break;} else {phi[i * p] = phi[i] * (p - 1);}}}for (int i = 1; i <= n; i++) {phi_sum[i] = phi_sum[i - 1] + phi[i];}
}int main() {int n;cin >> n;init_phi(n);long long ans = 0;for (int d = 1; d <= n; d++) {int m = n / d;ans += (long long)d * (2 * phi_sum[m] - 1);}cout << ans << endl;return 0;
}