ZOJ 3435 Ideal Puzzle Bobble(gcd(i,j,k)=1/莫比乌斯反演)

题目链接：
ZOJ 3435 Ideal Puzzle Bobble
题意：

$$\sum_{i=0}^{i=a}\sum_{j=0}^{j=b}\sum_{k=0}^{k=c}[gcd(i,j,k)==1],a,b,c\in [1,1000000]$$
分析；
$1.$当 $i=j=k=0$时是不成立的。
$2.$当 $i,j,k$中有两个为 $0$时,只有三种情况 $(0,0,1),(0,1,0),(1,0,0)$.
$3.$当 $i,j,k$中有一个为 $0$时,相当于求 $gcd(i,j)=1,gcd(i,k)=1,gcd(j,k)=1)$的对数。
$4.$当 $i,j,k$均大于 $0$时，相当于求 $gcd(i,j,k)=1(i\in [1,a],j\in[1, b],k\in[1,c])$的对数。
对于 $3.4$两种情况用莫比乌斯反演即可。

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <bitset>
using namespace std;
typedef long long ll;
const int MAX_N = 1000010;int prime_cnt, prime[MAX_N], mu[MAX_N];
ll sum[MAX_N];
bitset<MAX_N> bs;void GetMu()
{prime_cnt = 0;bs.set();mu[1] = 1;for(int i = 2; i < MAX_N; ++i) {if(bs[i]) {prime[prime_cnt++] = i;mu[i] = -1;}for(int j = 0; j < prime_cnt && i * prime[j] < MAX_N; ++j) {bs[i * prime[j]] = 0;if(i % prime[j]) {mu[i * prime[j]] = - mu[i];}else {mu[i * prime[j]] = 0;           break;}}}for(int i = 1; i < MAX_N; ++i) {sum[i] = sum[i - 1] + mu[i];}
}int main()
{GetMu();int a, b, c;while(~scanf("%d%d%d", &a, &b, &c)){a--, b--, c--;if(a > b) swap(a, b);if(a > c) swap(a, c);if(b > c) swap(b, c);// a <= b <= cll ans = 3, tmp;int last, x, y, z;for(int i = 1; i <= b; i = last + 1) {
   //注意枚举的范围last = i;x = a / i, y = b / i, z = c / i;if(i <= a){last = min(a / x, b / y);last = min(last, c / z);}else {
   //防止出现除以0last = min(b / y, c / z);}tmp = (ll) x * y * z + (ll)x * y + (ll)x * z + (ll)y * z;ans += tmp * (sum[last] - sum[i - 1]);}printf("%lld\n", ans);  }return 0;
}