【SPOJ 7001】VLATTICE

题目传送门：http://www.spoj.com/problems/VLATTICE/
离线版题目：http://paste.ubuntu.com/20300942/

仪仗队升级版！
然而还是不会QAQ 还是可耻地看了题解QAQ

#include<iostream>
#include<cstdio>
#include<bitset>
#define LL long long
using namespace std;

const int MAXN = 1000000+9;
const int MX = 1000000;

int pri[MAXN],tot,mu[MAXN];
bitset<MAXN> tag;

inline void Get_mu(){
	mu[1] = 1;
	for (int i=2;i<=MX;i++) {
		if (!tag[i]) pri[++tot] = i, mu[i] = -1;
		for (int j=1;j<=tot && i*pri[j]<=MX;j++){
			tag[i*pri[j]] = 1;
			if (i % pri[j]) mu[i*pri[j]] = -mu[i];
			else {mu[i*pri[j]]=0; break;}
		}
	}
	for (int i=1;i<=MX;i++) mu[i] += mu[i-1];
}

int main(){
	Get_mu(); int n,T,tmp; cin>>T;
	while (T--) {
		scanf("%d",&n); LL vout = 0;
		for (int i=1;i<=n;i=tmp+1){
			tmp = n/(n/i);
			vout += (LL)(mu[tmp]-mu[i-1])*(n/i)*(n/i);
		} vout = vout*3+3;
		for (int i=1;i<=n;i=tmp+1){
			tmp = n/(n/i);
			vout += (LL)(mu[tmp]-mu[i-1])*(n/i)*(n/i)*(n/i);
		}
		printf("%lld\n",vout); 
	}
	return 0;
} 

—– UPD 2016.9.21 —–
今天和同学们讨论这个题目的时候
发现，这题根本不需要莫比乌斯反演嘛 (╯‵□′)╯︵┻━┻
\(\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {\sum\limits_{k = 1}^n {[\gcd (i,j,k) = 1] = } } } \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {\sum\limits_{k = 1}^n {\sum\limits_{d|\gcd (i,j,k)} {\mu (d)} = \sum\limits_{d = 1}^n {\mu (d) \cdot {{\left\lfloor {\frac{n}{d}} \right\rfloor }^3}} } } } \)