一、题目描述

二、算法分析说明与代码编写指导

观察，写出递推式 F[n] = F[n - 1] ∪ { i / n | gcd(i, n) = 1 }。可见 |F[n]| = |F[n - 1]| + φ(n)，认为 φ(1) = 0。
打表生成 1 ~ 1e6 的欧拉函数的值后，记 S[n] = φ(1) + φ(2) + … + φ(n)，求得前缀和。

三、AC 代码（266 ms）

#include<cstdio>
#pragma warning(disable:4996)
unsigned long long phi[1000001], n, s[1000001];
template<class _Pty> inline void gen_phi(_Pty* const phi, const _Pty& n) {
	_Pty m = n / 2;
	for (_Pty i = 2; i <= m; ++i) {
		if (!phi[i]) {
			for (_Pty j = i; j <= n; j += i) {
				if (!phi[j])phi[j] = j;
				phi[j] = phi[j] / i * (i - 1);
			}
		}
	}
	for (_Pty i = m + 1; i <= n; ++i)
		if (!phi[i]) { phi[i] = i - 1; }
}
int main() {
	gen_phi(phi, 1000000ull);
	for (unsigned i = 1; i <= 1000000; ++i)s[i] = s[i - 1] + phi[i];
	for (;;) {
		scanf("%llu", &n); if (n == 0)return 0;
		printf("%llu\n", s[n]);
	}
}