题目大意
给定一个 \(N×N×N\) 的由若干点组成的立方体，点的坐标从 \((0,0,0)\) 到 \((N,N,N)\)，求从点 \((0,0,0)\) 处可以看见多少个点。
思路分析
我们将立方体上的点分成三类：
- 在 \(xy,yz,xz\) 平面上的点。
- 在 \(x,y,z\) 轴上的点。
- 即不在平面，也不在坐标轴上的点。
就可以简单得出我们需要求的式子：
\[\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n[\gcd(i,j,k)=1]+3\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]+3
\]
然后就可以开始愉快的颓柿子了：
\[\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n[\gcd(i,j,k)=1]\\&=\sum_{d=1}^n\mu(d)\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n[d|i][d|j][d|k]\\&=\sum_{d=1}^n\mu(d)\lfloor\frac{n}{d}\rfloor^3\end{aligned}
\]
类似的，
\[\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]\\&=\sum_{d=1}^n\mu(d)\sum_{i=1}^n\sum_{j=1}^m[d|i][d|j]\\&=\sum_{d=1}^n\mu(d)\lfloor\frac{n}{d}\rfloor^2\end{aligned}
\]
因此，我们的答案就是：
\[3+\sum_{d=1}^n\mu(d)\lfloor\frac{n}{d}\rfloor^2(\lfloor\frac{n}{d}\rfloor+3)
\]
只需要线性筛出 \(\mu\) 的前缀和，再通过整除分块就可以在 \(O(\sqrt n)\) 的时间复杂度内得出结果。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1111111,L=1000000;
#define int long long\\好习惯
int T,n,ans,cnt;
int v[N],prime[N],mu[N];
void sieve(){
mu[1]=1;
for(int i=2;i<=L;i++){
if(!v[i]){prime[++cnt]=i;mu[i]=-1;}
for(int j=1;j<=cnt&&i*prime[j]<=L;j++){
v[i*prime[j]]=1;
if(i%prime[j]==0) break;
mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=L;i++) mu[i]+=mu[i-1];\\计算前缀和
}
signed main(){
sieve();
scanf("%lld",&T);
while(T--){
scanf("%lld",&n);
ans=0;
for(int l=1,r;l<=n;l=r+1){//简单的整除分块
r=n/(n/l);
ans+=(mu[r]-mu[l-1])*((n/l)*(n/l)*(3+(n/l)));\\根据式子计算结果
}ans+=3;
cout<<ans<<'\n';
}
return 0;
}