VLATTICE – Visible Lattice Points
no tags
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 NOutput :Output T lines, one corresponding to each test case.Sample Input :3125Sample Output :719175Constraints :T <= 501 <= N <= 1000000
/* ***********************************************Author:CKbossCreated 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;}
，人总是珍惜未得到的，而遗忘了所拥有的
