bzoj 2818.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
#define intl long long
#define maxn 10000100
using namespace std;
int i,j,k,l,m,n,top;
int pri[maxn],done[maxn];
intl phi[maxn],ans;
int main() {
	freopen("2818.in","r",stdin);
	freopen("2818.out","w",stdout);
	scanf("%d",&n);
	for (i = 2; i <= n; i++) {
		if (!done[i]) {
			pri[++top] = i;
			phi[i] = (intl) (i - 1);
		}
		for (j = 1; j <= top && i * pri[j] <= n; j++) {
			done[i * pri[j]] = 1;
			if (!(i % pri[j])) {
				phi[i * pri[j]] = phi[i] * (intl) pri[j];
				break;
			}
			else phi[i * pri[j]] = phi[i] * (intl) (pri[j] - 1);
		}
	}
	for (i = 1; i <= n; i++) phi[i] += phi[i - 1];
	for (i = 1; i <= top; i++) {
		ans += phi[n / pri[i]];
	}
	(ans *= (intl) 2) += (intl) top;
	printf("%lld",ans);
	return 0;
}