这个题是根据某个二维平面的题改编过来的。
首先把问题转化一下， 就是你站在原点(0, 0, 0)能看到多少格点。
答案分为三个部分：
- 八个象限里的格点，即 gcd(x, y, z) = 1，且xyz均不为0. 可以先假设xyz都是整数，然后将所求的答案乘8
- 12个四分之一平面中的点，可以先算(x, y, 0)(x > 0, y > 0)这样的点的个数，然后乘12
- 坐标轴上距原点距离为1的6个点
三维对应的莫比乌斯公式就是：
在这道题里面就是 X = Y = Z = N / 2
这道题用容斥原理或者欧拉函数也可以做，但是还是莫比乌斯反演最好写最快了。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL; const int maxn = ;
int prime[maxn + ], mu[maxn + ];
bool vis[maxn + ]; void Mobius()
{
mu[] = ;
int cnt = ;
for(int i = ; i <= maxn; i++)
{
if(!vis[i]) { mu[i] = -; prime[cnt++] = i; }
for(int j = ; j < cnt && (LL)i*prime[j] <= maxn; j++)
{
vis[i * prime[j]] = ;
if(i % prime[j] != ) mu[i*prime[j]] = -mu[i];
else { mu[i*prime[j]] = ; break; }
}
} for(int i = ; i <= maxn; i++) mu[i] += mu[i - ];
} int main()
{
Mobius(); int n, kase = ;
while(scanf("%d", &n) == && n)
{
n /= ;
LL ans = ;
for(int i = , j; i <= n; i = j + )
{
int t = n / i;
j = n / t;
ans += ((LL)t*t*t* + (LL)t*t*) * (mu[j] - mu[i - ]);
}
printf("Crystal %d: %lld\n", ++kase, ans);
} return ;
}
代码君