[ZOJ3435] Ideal Puzzle Bobble (莫比乌斯反演,数论分块)

发布于 2018-01-12  14 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[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?

Http

zoj

Tag

莫比乌斯反演,数论分块

题目大意

在空间坐标系的第一卦限给定L*H*W的范围,问从(1,1,1)这个点看去,能看到多少个不被遮住的整数点?

解决思路

这一题有些类似,都是求\sum_{i}^{L} \sum_{j}^{H} \sum_{k}^{W} [gcd(i,j,k)==1] ,但本题不同的地方是,这里是从(1,1,1)看的,所以可以考虑把整个立体空间平移到(0,0,0),即把L,H,W都减一。
那么我们把整个立体空间分为三个部分考虑。
第一部分是三根正轴,我们定义为L轴,H轴和W轴,很容易知道这三根数轴上面的贡献分别是1
第二部分是三个平面:LoH,HoW,LoR,三个平面分别的贡献是\sum_{i} \sum_{j} [gcd(i,j)==1]
第三部分就是除去三个平面和三根数轴剩下的L*H*W的空间,根据上面的式子,我们知道是求\sum_{i}^{L} \sum_{j}^{H} \sum_{k}^{W} [gcd(i,j,k)==1]
然后我们考虑如何将上面的式子化简,先来看三维的情况
设\[F(x)=\sum_{i}^{L} \sum_{j}^{H} \sum_{k}^{W} [gcd(i,j,k)==x] \] \[G(x)=\sum_{x|d} F(d)=\sum_{x|d} \sum_{i}^{L} \sum_{j}^{H} \sum_{k}^{W} [gcd(i,j,k)==d] \]可以发现,与上面那一题类似的,\[G(x)=\lfloor \frac{L}{x} \rfloor * \lfloor \frac{H}{x} \rfloor * \lfloor \frac{W}{x} \rfloor \]
好,那么根据莫比乌斯反演,可以得到\[F(x)=\sum_{x|d} \mu (\frac{d}{x}) G(d)\] 最终得到\[F(1)=\sum_{i=1}^n \mu (i) \lfloor \frac{L}{i} \rfloor * \lfloor \frac{H}{i} \rfloor * \lfloor \frac{W}{i} \rfloor\]
那么相应的,二维的情况就是\[\sum_{i=1}^n \mu (i) \lfloor \frac{L}{i} \rfloor * \lfloor \frac{H}{i} \rfloor \]
虽然说我们把O(n^3)的复杂度降到了O(n),但是这还不够,因为题目有多组数据。怎么办呢?我们来看到这组例子。
\[\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 \\ ……\]
我们发现,对于n==100的时候,i=21,22,23,24,25时的代价是一样的,并且这个相同的区间在i变大的时候,区间也会越来越大。
这就是数论分块的原理:考虑把一样的东西一起做。\lfloor \frac{n}{\frac{n}{i}} \rfloor这样就可以找到与i在同一区间(同一个块)的最后一个位置,利用提前计算好的\mu(i)的前缀和,就可以一个区间一个区间地算了

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[ZOJ3435] Ideal Puzzle Bobble (莫比乌斯反演,数论分块)


HNCJ OIer 一枚