题目
题解
这里有个弱化版本.
在二维上，如果 \((x,y)\) 在 \((0,0)\) 可视，那么有 \(\gcd(x,y)=1\)，即这俩数互质，虽然这道题在三维视角上，但是也是一样的.
现在，我们的任务就是求：使得 \(\gcd(a,b,c)=1\) 的三元组 \(\lang a,b,c\rang\) 的个数是多少.
使用同样的套路，定义 \(F(d)\) 表示 \((a,b,c)\) 为 \(d\) 的倍数的三元组个数，再定义 \(f(a,b,c)\) 为 \((a,b,c)\) 刚刚好为 \(d\) 的三元组个数，那么有
\[F(d)=\sum_{d|n}f(n) \]同时也有
\[F(d)=\left \lfloor \frac{n}{d} \right\rfloor^3 \]那么，反演一下有
\[f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d) \]我们要求的是 \(f(1)\)，对于 \(f(1)\) 有
\[f(1)=\sum_{d=1}^{n}\mu(d)F(d) \]整除分块即可.
但是，我们还要考虑三个面上的情况，这就是退化到二维的情形了，再推一个式子即可（其实就是三次方变二次方，没啥必要推的）
记得最后加上三个特殊点——\(\lang 0,0,1\rang,\;\lang 0,1,0\rang,\;\lang 1,0,0\rang\) 的贡献.
总而言之，实际上我们要求的就是
\[\sum_i^n\sum_j^n\sum_k^n[\gcd(a,b,c)=1]+3\sum_i^n\sum_j^n[\gcd(i,j)=1]+3 \]这个式子.
代码
inline ll pow3(const ll x){
return x * x * x;
}
inline ll pow2(const ll x){
return x * x;
}
inline ll f(const int n){
ll ret = 0;
for(int l = 1, r; l <= n; l = r + 1){
r = n / (n / l);
ret += 1ll * (pre[r] - pre[l - 1]) * pow3(n / l);
}
return ret;
}
inline ll g(const int n){
ll ret = 0;
for(int l = 1, r; l <= n; l = r + 1){
r = n / (n / l);
ret += 1ll * (pre[r] - pre[l - 1]) * pow2(n / l);
}
return ret;
}
signed main(){
sieve();
rep(i, 1, maxn) pre[i] = pre[i - 1] + mu[i];
int T = readin(1);
while(T --){
int n = readin(1);
writc(f(n) + 3 * g(n) + 3, '\n');
}
return 0;
}