SPOJ VLATTICE.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 1001000
#define N 1000010
#define intl long long
using namespace std;
int i,j,k,l,m,n,top,T,t;
int mu[maxn],pri[maxn],done[maxn],mark[maxn];
intl ans;
intl S(int a) { return (intl) a * (intl) a * (intl) a; }
intl s(int a) { return (intl) a * (intl) a; }

int main() {
	freopen("pro.in","r",stdin);
	freopen("pro.out","w",stdout);
	for (i = 2; i <= N; i++) {
		if (!mark[i]) {
			pri[++top] = i;
			mu[i] =-1;
		}
		
		for (j = 1; j <= top && pri[j] * i <= N; j++) {
			mark[pri[j] * i] = 1;
			if (i % pri[j]) 
				mu[i * pri[j]] = -mu[i];
			else break;
		}
	}
	mu[1] = 1;
	scanf("%d",&T);
	for (; T; T--) {
		scanf("%d",&n); ans = 0;
		for (i = 1; i <= n; i++)
			ans += (intl) mu[i] * S(n / i);
		for (i = 1; i <= n; i++)
			ans += (intl) mu[i] * s(n / i) * (intl) 3;
		printf("%lld\n",ans + (intl) 3);
	}
	return 0;
}