自认为正确的题解里好像没有的90分做法(WA了一个点)

#include <cstdio>

typedef long long ll;

const int N = 2000010;

int n;
int prime[N], phi[N], cnt;
bool p[N];
ll sphi[N], ans;

void sieve() {
	prime[1] = 2;
	phi[1] = 1;
	for (int i = 1; i <= n; i++) p[i] = 1;
	for (int i = 2; i < n; i++) {
		if (p[i]) {
			prime[++cnt] = i;
			phi[i] = i - 1;
		}
		for (int j = 1; i * prime[j] <= n && j <= cnt; j++) {
			p[i * prime[j]] = 0;
			if (i % prime[j] == 0) {
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			phi[i * prime[j]] = phi[i] * phi[prime[j]];
		}
	}
}

int main() {
	scanf("%d", &n);
	sieve();
	sphi[1] = phi[1];
	for (int i = 2; i <= n; i++) sphi[i] = sphi[i - 1] + phi[i];
	for (int i = 1; i <= n; i++) ans += i * sphi[n / i];
	ans -= n * (n + 1) / 2;
	printf("%lld", ans);
	return 0;
}