# [ZOJ3435] Ideal Puzzle Bobble （莫比乌斯反演，数论分块）

### Description

Have you ever played Puzzle Bobble, a very famous PC game? In this game, as a very cute bobble dragon, you must keep shooting powerful bubbles to crush all the colorful bubbles upwards. Victory comes when all the bubbles upwards are crushed.

Little Tom is crazy about this game. One day, he finds that all kinds of Puzzle Bobble are 2D Games. To be more excited when playing this game, he comes up with a new idea to design a 3D Puzzle Bobble game! In this game, the bobble dragon is standing in a cubic room with L in length, W in width and H in height. Around him are so many colorful bubbles. We can use 3D Cartesian coordinates (x, y, z) to represent the locations of the bobble dragon and those bubbles. All these coordinates (x, y, z) are triple positive integers ranged from (1, 1, 1) to (L, W, H).

To simplify the problem, let's assume the bobble dragon is standing at (1, 1, 1) in the room. And there is one colorful bubble at every (x, y, z) in the room except (1, 1, 1). The dragon is so strong that he can shoot out a magical bubble to crush all the colorful bubbles in the straight line which the magical bubble flies every single time. Note that bubbles are significantly small with respect to the distances between each two bubbles. Our question remains, how many magical bubbles will the cute dragon shoot before crushing all the colorful bubbles around him?

zoj

## 解决思路

$\lfloor \frac{100}{20} \rfloor =5 \\ \lfloor \frac{100}{21} \rfloor =\lfloor \frac{100}{22} \rfloor =\lfloor \frac{100}{23} \rfloor =\lfloor \frac{100}{24} \rfloor =\lfloor \frac{100}{25} \rfloor =4 \lfloor \frac{100}{26} \rfloor =3 \\ ……$

## 代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxNum=1000010;
const int inf=2147483647;

int n;
ll Mu[maxNum],SumMu[maxNum];
int pricnt=0,Prime[maxNum];
bool notprime[maxNum];
int L,W,H;

void GetMu();

int main()
{
GetMu();
while (scanf("%d%d%d",&L,&W,&H)!=EOF)
{
L--;W--;H--;
ll ans=3;
int limit=min(L,min(W,H));
for (int i=1,last=1;i<=limit;i=last+1)
{
ll k1=L/i,k2=W/i,k3=H/i;
last=min(L/k1,min(W/k2,H/k3));
ans=ans+(SumMu[last]-SumMu[i-1])*k1*k2*k3;
}
limit=min(L,W);
for (int i=1,last=1;i<=limit;i=last+1)
{
ll k1=L/i,k2=W/i;
last=min(L/k1,W/k2);
ans=ans+(SumMu[last]-SumMu[i-1])*k1*k2;
}
limit=min(L,H);
for (int i=1,last=1;i<=limit;i=last+1)
{
ll k1=L/i,k2=H/i;
last=min(L/k1,H/k2);
ans=ans+(SumMu[last]-SumMu[i-1])*k1*k2;
}
limit=min(W,H);
for (int i=1,last=1;i<=limit;i=last+1)
{
ll k1=W/i,k2=H/i;
last=min(W/k1,H/k2);
ans=ans+(SumMu[last]-SumMu[i-1])*k1*k2;
}
printf("%lld\n",ans);
}
return 0;
}

void GetMu()
{
notprime[1]=1;Mu[1]=1;
for (int i=2;i<maxNum;i++)
{
if (notprime[i]==0) Prime[++pricnt]=i,Mu[i]=-1;
for (int j=1;(j<=pricnt)&&((ll)i*(ll)Prime[j]<maxNum);j++)
{
notprime[i*Prime[j]]=1;
if (i%Prime[j]!=0) Mu[i*Prime[j]]=-Mu[i];
else break;
}
}
for (int i=1;i<maxNum;i++) SumMu[i]=SumMu[i-1]+Mu[i];
return;
}


HNCJ OIer