UVa 11014 (莫比乌斯反演) Make a Crystal

这个题是根据某个二维平面的题改编过来的。

首先把问题转化一下，就是你站在原点(0, 0, 0)能看到多少格点。

答案分为三个部分：

八个象限里的格点，即 gcd(x, y, z) = 1，且xyz均不为0. 可以先假设xyz都是整数，然后将所求的答案乘8
12个四分之一平面中的点，可以先算(x, y, 0)(x > 0, y > 0)这样的点的个数，然后乘12
坐标轴上距原点距离为1的6个点

三维对应的莫比乌斯公式就是： $\sum \mu(d)\left \lfloor \frac{X}{d} \right \rfloor \left \lfloor \frac{Y}{d} \right \rfloor \left \lfloor \frac{Z}{d} \right \rfloor$

在这道题里面就是 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 ;

 }

代码君

巴特西

UVa 11014 (莫比乌斯反演) Make a Crystal

最新文章

热门文章