记录编号	600136	评测结果	AATTTTTTTT
题目名称	[BZOJ 2818]GCD	最终得分	20
用户昵称	喵喵喵	是否通过	未通过
代码语言	C++	运行时间	15.241 s
提交时间	2025-04-16 20:00:13	内存使用	12.66 MiB

#include <bits/stdc++.h>
#define herta return 0;
using namespace std;
int N;
int ans;
bool v[10000005];
void primes(int n) {
	for (int i = 2; i <= n; ++i) v[i] = 1;
	for (int i = 2; i <= n; ++i) {
		if (!v[i]) continue;
		for (int j = i; j <= n / i; ++j)
			v[i * j] = 0;
	}
}
int main() {
	freopen("gcd_prime.in", "r", stdin);
	freopen("gcd_prime.out", "w", stdout);
	primes(10000000);
	cin >> N;
	for (int x = 1; x <= N; x++) {
		if(v[x]) ans++;
		for (int y = x + 1; y <= N; y++) {
			if (v[__gcd(x,y)]) ans++;
			if (x != y && v[__gcd(x,y)]) ans++;
		}
	}
	cout << ans << endl;
	herta
}