2010-1113

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<blockquote><p>
题目去掉背景以后就是要求#{(i, j, k) | gcd(i, j, k) = 1, i ≤ L, j ≤ W, k ≤ H}。
</p></blockquote>
<p>
规模1e6，暴力显然是不行的。首先对于<a href="http://acm.hdu.edu.cn/showproblem.php?pid=1695" target="_blank">gcd(x, y) = 1</a>这个问题，可以直接利用容斥原理(<a href="http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle" target="_blank">Inclusion–exclusion principle</a>)得到解决。类似的，记f(x)表示gcd(i, j, k)整除x的个数，那么利用容斥原理有answer := f(1) – f(2) – f(3) – … – f(p) + f(2*3) + f(2*5) + … + f(p1*p2) – f(2*3*5) – …。事实上这个玩意是有名字的，叫做默比乌斯函数<a href="http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula" target="_blank">Möbius inversion formula</a>。然后显然有f(n)=(i/n)(j/n)(k/n)，这里的/是整数除法。至此，我们推出的这玩意在一维的情况其实就是默比乌斯反演公式(<a href="http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula" target="_blank">Möbius inversion formula</a>)，不过我总记不住，每次都是重新推。于是我们知道答案就是<br>

</p><center><img src="http://s.wordpress.com/latex.php?latex=%20%5Csum_%7Bn%3D0%7D%5E%5Cinfty%5Cmu%28n%29%5Clfloor%5Cfrac%7Bi%7D%7Bn%7D%5Crfloor%5Clfloor%5Cfrac%7Bj%7D%7Bn%7D%5Crfloor%5Clfloor%5Cfrac%7Bk%7D%7Bn%7D%5Crfloor&amp;bg=T&amp;fg=000000&amp;s=0" alt=" \sum_{n=0}^\infty\mu(n)\lfloor\frac{i}{n}\rfloor\lfloor\frac{j}{n}\rfloor\lfloor\frac{k}{n}\rfloor" title=" \sum_{n=0}^\infty\mu(n)\lfloor\frac{i}{n}\rfloor\lfloor\frac{j}{n}\rfloor\lfloor\frac{k}{n}\rfloor" class="latex"></center><br>
这个公式应该是没有closed form的（这玩意要有closed form，必然会被搜<a href="http://oeis.org/" target="_blank">OEIS</a>的同学秒了，所以我出monthly的时候都会把此类题毙掉），不过我们已经能在O(N)的时间解决这道题了，事实上不只是三维，来个十维八维都不成问题，嗯事实上这题也可以扩展到更高维。如果这题是单case的话，到这里就结束了，不过这题有很多很多case，题目要求一个更高效的算法。做法就是合并(i/n)(j/n)(k/n)相同的项，即枚举商，比如<a href="http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=3207" target="_blank">这个</a>求<img src="http://s.wordpress.com/latex.php?latex=%5Csum_%7Bi%3D1%7D%5En%5Cleft%28%5Clfloor%5Cfrac%7Bn%7D%7Bx%7D%5Crfloor-1%5Cright%29&amp;bg=T&amp;fg=000000&amp;s=0" alt="\sum_{i=1}^n\left(\lfloor\frac{n}{x}\rfloor-1\right)" title="\sum_{i=1}^n\left(\lfloor\frac{n}{x}\rfloor-1\right)" class="latex">的问题，很容易证明这个复杂度是O(\sqrt{N})的。这样我们事先求出默比乌斯函数函数的部分和（哦，这玩意也有名字，叫Mertens function），这部分只要通过素数筛法可以O(n)的预处理得到，然后对于(i/n)(j/n)(k/n)相同一段的和就可以O(1)得到，由于这样的段数不超过O(3\sqrt{N})，所以对于每个case，只要O(\sqrt{N})的时间求解。


}}}

http://watashi.ws/blog/1622/zojmonthly1011/

题目去掉背景以后就是要求#{(i, j, k) | gcd(i, j, k) = 1, i ≤ L, j ≤ W, k ≤ H}。

规模1e6，暴力显然是不行的。首先对于gcd(x, y) = 1这个问题，可以直接利用容斥原理(Inclusion–exclusion principle)得到解决。类似的，记f(x)表示gcd(i, j, k)整除x的个数，那么利用容斥原理有answer := f(1) – f(2) – f(3) – … – f(p) + f(2*3) + f(2*5) + … + f(p1*p2) – f(2*3*5) – …。事实上这个玩意是有名字的，叫做默比乌斯函数Möbius inversion formula。然后显然有f(n)=(i/n)(j/n)(k/n)，这里的/是整数除法。至此，我们推出的这玩意在一维的情况其实就是默比乌斯反演公式(Möbius inversion formula)，不过我总记不住，每次都是重新推。于是我们知道答案就是

$\sum_{n=0}^\infty\mu(n)\lfloor\frac{i}{n}\rfloor\lfloor\frac{j}{n}\rfloor\lfloor\frac{k}{n}\rfloor$
这个公式应该是没有closed form的（这玩意要有closed form，必然会被搜OEIS的同学秒了，所以我出monthly的时候都会把此类题毙掉），不过我们已经能在O(N)的时间解决这道题了，事实上不只是三维，来个十维八维都不成问题，嗯事实上这题也可以扩展到更高维。如果这题是单case的话，到这里就结束了，不过这题有很多很多case，题目要求一个更高效的算法。做法就是合并(i/n)(j/n)(k/n)相同的项，即枚举商，比如这个求 $\sum_{i=1}^n\left(\lfloor\frac{n}{x}\rfloor-1\right)$ 的问题，很容易证明这个复杂度是O(\sqrt{N})的。这样我们事先求出默比乌斯函数函数的部分和（哦，这玩意也有名字，叫Mertens function），这部分只要通过素数筛法可以O(n)的预处理得到，然后对于(i/n)(j/n)(k/n)相同一段的和就可以O(1)得到，由于这样的段数不超过O(3\sqrt{N})，所以对于每个case，只要O(\sqrt{N})的时间求解。

http://watashi.ws/blog/1622/zojmonthly1011/