记录编号	600575	评测结果	AAAAAAAAAA
题目名称	2602.[BZOJ 2818]GCD	最终得分	100
用户昵称	对立猫猫对立	是否通过	通过
代码语言	C++	运行时间	0.640 s
提交时间	2025-05-07 21:13:23	内存使用	38.96 MiB

#include <cstdio>
#include <vector>
typedef long long ll;
using namespace std;
const int MAXN = 1e7 + 10;
bool vis[MAXN];
vector <ll> primes;
ll phi[MAXN], pre[MAXN];
void solve(int n) {
	phi[0] = 0, phi[1] = 1;
	for (int i = 2; i <= n; ++i) {
		if (!vis[i]) primes.push_back(i), phi[i] = i - 1;
		for (auto p : primes) {
			if (i * (long long)p > n) break;
			vis[i * p] = 1;
			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) {
		pre[i] = pre[i - 1] + phi[i];
	}
}
int n;
ll ans;
int main() {
	freopen("gcd_prime.in", "r", stdin);
	freopen("gcd_prime.out", "w", stdout);
	scanf("%d", &n);
	solve(n);
	for (auto p : primes) {
		ans += 2 * pre[n / p] - 1;
	}
	printf("%lld", ans);
	return 0;
}