Visible Lattice Points
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
//2017-08-04
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; const int N = ;
int mu[N], prime[N], tot, phi[N];
long long plane[N];
bool book[N]; void Moblus()//求出莫比乌斯函数
{
memset(book,false,sizeof(book));
mu[] = ;
int tot = ;
for(int i = ; i <= N; i++){
if(!book[i]){
prime[tot++] = i;
mu[i] = -;
}
for(int j = ; j < tot; j++){
if(i * prime[j] > N) break;
book[i * prime[j]] = true;
if( i % prime[j] == ){
mu[i * prime[j]] = ;
break;
}else{
mu[i * prime[j]] = -mu[i];
}
}
}
} void getphi()
{
int i,j;
phi[]=;
for(i=;i<=N;i++)//相当于分解质因式的逆过程
{
if(!book[i])
{
prime[++tot]=i;//筛素数的时候首先会判断i是否是素数。
phi[i]=i-;//当 i 是素数时 phi[i]=i-1
}
for(j=;j<=tot;j++)
{
if(i*prime[j]>N) break;
book[i*prime[j]]=;//确定i*prime[j]不是素数
if(i%prime[j]==)//接着我们会看prime[j]是否是i的约数
{
phi[i*prime[j]]=phi[i]*prime[j];break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-);//其实这里prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性
}
}
} int main()
{
int T, n;
scanf("%d", &T);
Moblus();
getphi();
plane[] = ;
for(int i = ; i < N; i++){
plane[i] = plane[i-]+phi[i];
}
while(T--){
scanf("%d", &n);
long long ans = ;
for(int d = ; d <= n; d++){
int tmp = (int)(n/d);
ans += (long long)mu[d]*tmp*tmp*tmp;
}
ans += *(plane[n]*+);
printf("%lld\n", ans);
} return ;
}