7001. Visible Lattice PointsProblem code: VLATTICE |
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
这题就是求gcd(a,b,c) = 1 a,b,c <=N 的对数。
用莫比乌斯反演可以求解。
设g(n)为gcd(x,y,z)=n的个数，f(n)为n | g(i*n)的个数，那么有f(n)=sigma(n|d,g(d))，那么g(n)=sigma(n|d, mu(d/n)*f(d))，我们要求g(1)，则g(1)=sigma(n|d, mu(d)*f(d))，
因为f(d)=(n/d)*(n/d)*(n/d)，所以g(1)=sigma( mu(d)*(n/d)*(n/d)*(n/d) ).
/* ***********************************************
Author :kuangbin
Created Time :2013/8/21 18:28:50
File Name :F:\2013ACM练习\专题学习\数学\莫比乌斯反演\SPOJ7001.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int MAXN = ;
bool check[MAXN+];
int prime[MAXN+];
int mu[MAXN+];
void Moblus()
{
memset(check,false,sizeof(check));
mu[] = ;
int tot = ;
for(int i = ; i <= MAXN; i++)
{
if( !check[i] )
{
prime[tot++] = i;
mu[i] = -;
}
for(int j = ; j < tot; j++)
{
if(i * prime[j] > MAXN) break;
check[i * prime[j]] = true;
if( i % prime[j] == )
{
mu[i * prime[j]] = ;
break;
}
else
{
mu[i * prime[j]] = -mu[i];
}
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T,n;
Moblus();
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
long long ans = ;
for(int i = ;i <= n;i++)
ans += (long long)mu[i]*(n/i)*(n/i)*((n/i)+);
printf("%lld\n",ans);
}
return ;
}