题目传送门：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}} } } } \)
