| Time Limit: 1368MS | Memory Limit: 1572864KB | 64bit IO Format: %lld & %llu |
Description
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
Hint
题意：在一个边长为n的正方体内，从原点出发能够接触多少个点。
题解：
莫比乌斯反演。
首先，我们要把答案分三类讨论：
1, 坐标轴上的三个点可以看见(1,0,0)和(0,1,0)和(0,0,1)。
2, 与原点相邻的三个表面的点。在三个表面各反演一次，加起来即可。
3, 在三维空间中反演一次即可。
答案为三种情况的和。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000010
#define LL long long
int mu[MAXN+],prime[],qz[MAXN+],tot;
bitset<MAXN+> vis;
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
void getmu()
{
int i,j;
mu[]=;tot=;
for(i=;i<=MAXN;i++)
{
if(vis[i]==)
{
prime[++tot]=i;
mu[i]=-;
}
for(j=;j<=tot&&prime[j]*i<=MAXN;j++)
{
vis[prime[j]*i]=;
if(i%prime[j]==)
{
mu[prime[j]*i]=;
break;
}
mu[prime[j]*i]=-mu[i];
}
}
}
void Qz()
{
for(int i=;i<=MAXN;i++)qz[i]=qz[i-]+mu[i];
}
LL calc2(int n)//计算平面上的个数.
{
int d,pos;
LL sum=;
for(d=;d<=n;d=pos+)
{
pos=n/(n/d);
sum+=(LL)(qz[pos]-qz[d-])*(n/d)*(n/d);
}
return sum;
}
LL calc3(int n)//计算空间里的个数.
{
int d,pos;
LL sum=;
for(d=;d<=n;d=pos+)
{
pos=n/(n/d);
sum+=(LL)(qz[pos]-qz[d-])*(n/d)*(n/d)*(n/d);
}
return sum;
}
int main()
{
int N,T;
T=read();
getmu();
Qz();
while(T--)
{
N=read();
printf("%lld\n",calc3(N)+calc2(N)*+);
}
fclose(stdin);
fclose(stdout);
return ;
}