VLATTICE - 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
Description(题意)
有
N*N*N网格.
一个角落在 (0,0,0)，对顶角落是
(N,N,N). 问从(0,0,0)看有多少个格点是可见的？点
X从点Y可见，当且仅当，线段XY上没有其他的点。
Input:
第一行是测试数据个数T。接着有T行每行有一个整数
N.
Output :
输出T行，每行是对应的可见格点的个数。
Sample Input :
3
1
2
5
Sample Output :
7
19
175
Constraints :
T <= 50
1 <= N <= 1000000
Solution:
#include<cstdio>
#include<iostream>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
typedef long long ll;
const int M=1e6+;
int n,m,T;ll sum[M];
int tot,prime[M/],mu[M];bool check[M];
void sieve(){
n=1e6;mu[]=;
for(int i=;i<=n;i++){
if(!check[i]) prime[++tot]=i,mu[i]=-;
for(int j=;j<=tot&&i*prime[j]<=n;j++){
check[i*prime[j]]=;
if(!(i%prime[j])){mu[i*prime[j]]=;break;}
else mu[i*prime[j]]=-mu[i];
}
}
for(int i=;i<=n;i++) sum[i]=sum[i-]+mu[i];
}
inline ll s2(int x){return 1LL*x*x;}
inline ll s3(int x){return 1LL*x*x*x;}
inline ll solve(int n){
ll ans=;
for(int i=,pos;i<=n;i=pos+){
pos=n/(n/i);
ans+=s3(n/i)*(sum[pos]-sum[i-]);
ans+=*s2(n/i)*(sum[pos]-sum[i-]);
}
return ans;
}
int main(){
sieve();
for(scanf("%d",&T);T--;){
scanf("%d",&n);
printf(LL"\n",solve(n));
}
return ;
}