Consider a N*N*N lattice. One corner is at (0,0,0) and the opposite one is at (N,N,N). How many lattice points are visible from corner at (0,0,0) ? A point X is visible from point Y iff no other lattice point lies
on the segment joining X and Y.
Input :
The first line contains the number of test cases T. The next T lines contain an interger N
Output :
Output T lines, one corresponding to each test case.
Sample Input :
3
1
2
5
Sample Output :
7
19
175
Constraints :
T <= 50
1 <= N <= 1000000
/* ***********************************************
Author :CKboss
Created Time :2015年03月26日 星期四 21时56分19秒
File Name :VLATTICE.cpp
************************************************ */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long int LL;
const int maxn = 1001000;
bool check[maxn];
int prime[maxn],mu[maxn];
void Moblus()
{
memset(check,true,sizeof(check));
mu[1]=1;
int tot=0;
for(int i=2;i<maxn;i++)
{
if(check[i])
{
prime[tot++]=i; mu[i]=-1;
}
for(int j=0;j<tot;j++)
{
int ij=prime[j]*i;
if(ij>maxn) break;
check[ij]=false;
if(i%prime[j]==0)
{
mu[ij]=0; break;
}
else mu[ij]=-mu[i];
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
Moblus();
int T_T;
cin>>T_T;
while(T_T--)
{
LL n;
cin>>n;
LL sum=3;
for(int i=1;i<=n;i++)
{
sum+=mu[i]*(n/i)*(n/i)*(n/i+3);
}
cout<<sum<<endl;
}
return 0;
}
SPOJ VLATTICE - Visible Lattice Points 莫比乌斯反演
原文：http://blog.csdn.net/ck_boss/article/details/44657329