记录编号	600467	评测结果	AAAAAAAAAA
题目名称	[BZOJ 2818]GCD	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	0.714 s
提交时间	2025-05-04 16:51:58	内存使用	38.97 MiB

#include <cstdio>
#include <vector>
typedef long long ll;
using ::std::vector;

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;
}