题目链接：

http://www.spoj.com/problems/VLATTICE/

题意：

1≤x,y,z≤n，问有多少对(x,y,z)使得gcd(x,y,z)=1

分析：

欧拉搞不了了，我们用莫比乌斯来搞一搞。

同样，我们设

f(d)：满足gcd(x,y,z)=d且x,y,z均在给定范围内的(x,y,z)的对数。

F(d)：满足d|gcd(x,y,z)且x,y,z均在给定范围内的(x,y,z)的对数。

显然F(d)=[n/d][n/d][n/d]，反演后我们得到

直接求解f(1)即可。

特别注意坐标轴上的点和坐标平面上的点。

代码：

/*

-- SPOJ 7001

-- mobius

-- Create by jiangyuzhu

-- 2016/5/30

*/

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <stack>

using namespace std;

typedef long long ll;

#define sa(n) scanf("%d", &(n))

#define sal(n) scanf("%I64d", &(n))

#define pl(x) cout << #x << " " << x << endl

#define mdzz cout<<"mdzz"<<endl;

const int maxn = 1e6 + 5 ;

int tot = 0;

int miu[maxn], prime[maxn], f[maxn];

bool flag[maxn];

void mobius()

{

    miu[1] = 1;

    tot = 0;

    for(int i = 2; i < maxn; i++){

        if(!flag[i]){

            prime[tot++] = i;

            miu[i] = -1;

        }

        for(int j = 0; j < tot && i * prime[j] < maxn; j++){

            flag[i * prime[j]] = true;

            if(i % prime[j]) miu[i * prime[j]] = -miu[i];

            else{

                miu[i * prime[j]] = 0;

                break;

            }

        }

    }

}

int main (void)

{

    mobius();

    int T;sa(T);

    int n;

    for(int kas = 1; kas <= T; kas++){

       scanf("%d", &n);

       ll ans = 3;

       for(int i = 1; i <= n; i++){

         ans += miu[i] * 1ll * (n/ i) * (n / i) * (n / i + 3);

       }

       printf("%lld\n", ans);

    }

    return 0;

}