题意：
从立方体点阵，从(0,0,0)到(N,N,N)，给定N求从(0,0,0)能看到的点的个数，其中能看到是指两点的连线的线段上没有其他的点。
题解：
题意可转换为从点(0,0,0)出发，以其余任一点结束，方向不同的向量数。
对于任一点(x,y,z)，若gcd(x,y,z)=d，其中d>1，则必存在点挡住了该点。
因此，其实最后要求的就是gcd(x,y,z)=1的(x,y,z)的数量。
对于三个坐标轴，有(0,0,1)，(0,1,0)，(1,0,0)三个点。
对于坐标轴两两之间围成的三个平面，有 个点，其中表示满足条件时为1，不满足条件时为0。
对于其余部分，有 个点。
因此所求为
基本的公式写完了，直接暴力肯定是不行的，剩下的就是要通过莫比乌斯反演将之化成可求解的形式。
设
其中为所有d的倍数n的的和
由莫比乌斯反演，则有
则
设
同理可得
综上
线性筛预处理出莫比乌斯函数，然后就可以对每组数据O(N)的求解了。
但是如果你掌握了数论分块，那么对每组数据的求解能做到。
设a1,a2,...,am是N的因子，从小到大。那么有，因为N至多有个因子，所以至多也只有个取值，可以分成块。
上面这段话有个小漏洞，应该说是，对于大于等于的因子满足上式，对于小于等于的数则每个块只有一个数，因此总的块的个数不超过。
那么我们可以在预处理的时候计算莫比乌斯函数的前缀和，求解每组数据时按块来计算，这样单组计算的时间复杂度即为。
预处理时间复杂度O(N)，因此总时间复杂度为
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define m_p make_pair
#define p_b push_back
#define For(i,a,b) for(int i=a;i<=b;i++)
#define ls (rt<<1)
#define rs ((rt<<1)|1)
#define mst(a,b) memset(a,b,sizeof(a))
const int MAXN=1e6+5;
const db eps=1e-8;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int seed=131;
int t,n;
bool notprime[MAXN];
int prime[MAXN],cnt,mu[MAXN];
void init(){notprime[1]=mu[1]=1;for(int i=2;i<MAXN;i++){if(!notprime[i]) prime[cnt++]=i,mu[i]=-1;for(int j=0;j<cnt&&prime[j]*i<MAXN;j++){notprime[i*prime[j]]=1;if(i%prime[j]==0) break;mu[i*prime[j]]=-mu[i];}}for(int i=2;i<MAXN;i++) mu[i]+=mu[i-1];
}
int main(){
// freopen("in.txt","r",stdin);init();cin>>t;while(t--){cin>>n;ll ans=3;for(int l=1,r,tt;l<=n;l=r+1){tt=n/l;r=n/tt;ans+=(mu[r]-mu[l-1])*tt*1ll*tt*(tt+3);}cout<<ans<<"\n";}return 0;
}