记录编号	533398	评测结果	AAAAAAAAAA
题目名称	[UVa 11426] 最大公约数之和——极限版II	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.941 s
提交时间	2019-06-23 18:51:40	内存使用	85.46 MiB

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#define LL long long

//线性筛1到n的素数以及欧拉函数,结果存放在prime和phi数组中，prime[0]存放素数个数
void get_phi(int n, int* prime, int* phi, bool* flag) {
	phi[1] = 1;
	for (int i = 2; i <= n; ++i) {
		if (!flag[i]) {
			phi[i] = i - 1;
			prime[++prime[0]] = i;
		}
		for (int j = 1; j <= prime[0] && i * prime[j] <= n; ++j) {
			flag[i * prime[j]] = 1;
			if (i % prime[j] == 0) {
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			else
				phi[i * prime[j]] = phi[i] * (prime[j] - 1);
		}
	}
}

int prime[5000010], phi[5000010];
bool flag[5000010];
LL sum[5000010];

LL cal(LL N) {
	LL ans = 0;
	for (LL i = 1, j; i <= N; i = j + 1) {
		j = N / (N / i);
		ans += (sum[j] - sum[i - 1]) * (N / i) * (N / i);
	}
	return ans;
}

int main() {
	freopen("gcd_extreme.in", "r", stdin);
	freopen("gcd_extreme.out", "w", stdout);
	get_phi(5000000, prime, phi, flag);
	for (int i = 1; i <= 5000000; ++i)
		sum[i] = sum[i - 1] + phi[i];

	LL N;
	for (scanf("%lld", &N); N; scanf("%lld", &N)) {
		LL ans = cal(N);
		ans -= (N + 1) * N >> 1;
		ans >>= 1;
		printf("%lld\n", ans);
	}
}