莫比乌斯反演
Q1 可见点
平面上有m*n个整点，他们的坐标(x, y)满足1<=x<=m, 1<=y<=n, x,y都是整数。求从原点能看到的点的数量(如果某点与原点的连线上没有其他点，则该点能被原点看到)。
\[ \sum_{i=1}^{m}\sum_{j=1}^{n}{[gcd(i,j)==1]} \]
Q2 能量收集
栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。
栋栋的植物种得非常整齐，一共有n列，每列有m棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标(x, y)来表示，其中x的范围是1至n，表示是在第x列，y的范围是1至m，表示是在第x列的第y棵。
由于能量汇集机器较大，不便移动，栋栋将它放在了一个角上，坐标正好是(0, 0)。
能量汇集机器在汇集的过程中有一定的能量损失。如果一棵植物与能量汇集机器连接而成的线段上有k棵植物，则能 量的损失为2k + 1。例如，当能量汇集机器收集坐标为(2, 4)的植物时，由于连接线段上存在一棵植物(1, 2)，会产生3的能量损失。注意，如果一棵植物与能量汇集机器连接的线段上没有植物，则能量损失为1。现在要计算总的能量损失。
这里是翻译成人话后的版本
在平面直角坐标系中，点(x,y)的代价定义为它和原点的连线中经过多少的其他整点个数*2+1。求横坐标在1~n且纵坐标在1~m的所有点的代价和。
\[ \sum_{i=1}^{m}\sum_{j=1}^{n}{[2gcd(i,j) -1]} \]
Q3 CountLines
确认过眼神, 还是熟悉的味道
x,y,z三个坐标都在0到n的范围内(包含边界) 这其中所有的整点每两个点确定一条直线,一共有多少条不同的直线？
\[
\sum_{x=1}^{n-1}\sum_{y=1}^{n-1}\sum_{z=1}^{n-1}{[gcd(x,y,z)==1]count(x,y,z,n)}
\] count(x,y,z,N)表示向量(x,y,z)在边长为n的立方体中生成的直线数目,传入的N=n+1
具体的计算公式可以参考另一篇文章
\[
f(x,y,z,N)=(N-x)(N-y)(N-z) \\
count(x,y,z,N)=
\begin{cases}
f(x,y,z,N) & \text{N≤2max(x,y,z)} \\
f(x,y,z,N)-f(2x,2y,2z,N) & \text{N>2max(x,y,z)} \\
\end{cases}
\]
这些题正面刚都会遇到数不尽的gcd(), 给访问过的gcd打个表也许能够以空间换时间吧
(为什么冥冥中感觉这句有点政治敏感??????)
但也不是太巧的办法
如果在一个规则的两重循环中, 形如\(\sum_{x=1}^{m}\sum_{y=1}^{n}\)需要调用gcd(), 考虑到周期性
对于每一个x可以只遍历1≤y≤x的, y>x的部分可以用周期性来解决
这样一来, 需要调用\({m(m-1)}\over{2}\)次gcd(), 并没有带来时间复杂度本质上的减少
这个时候就需要莫比乌斯大佬来教你做人了
约数版莫比乌斯反演:
若: \(f(n)=\sum_{d|n}g(d)\)
则: $g(n)=_{ab=n} μ (a)f(b) $倍数版莫比乌斯反演:
若: \(f(n)=\sum_{n|d}g(d)\)
则: $g(n)=_{d=kn} μ (k)f(d) $
其中的\(\mu(x)\)定义如下:
\[
\mu(x) =
\begin{cases}
1, & \text{x=1} \\
0, & \text{x有平方因子} \\
-1, & \text{x有奇数个因子} \\
1, & \text{x有偶数个因子}
\end{cases}
\]
难以理解是因为, 人们总希望以简单解构复杂, 而非由复杂解构简单
g(d)是难求的, 那么由很多g(d)累加得到的f(n)至少在形式上是复杂的
而f(n)在计算上却未必比g(d)难
由复杂解构简单, 需要你有构造的能力
借由第一个问题解释吧:
不妨记\(g(d)=\sum_{i=1}^{m}\sum_{j=1}^{n}{[gcd(i,j)==d]}\)
根据想用的第二组反演公式, f(x)应该是若干个g(x)的和。
记N=min(n,m)，也就是gcd的上限
\(f(d)=g(d)+g(2d)+g(3d)+...+g(⌊\frac{N}{d}⌋d)\)
\(f(d)=\sum_{i=1}^{m}\sum_{j=1}^{n}{[gcd(i,j)\%d==0]}\)
f(x)指的是满足gcd(i,j)是d的倍数的数对的个数
显然有\(f(x)=⌊\frac{n}{x}⌋⌊\frac{m}{x}⌋\)
此时有\(f(d)=\sum_{d|p}g(p)\quad (p<=N)\)
反演得到 $g(d)=_{p=kd<N} μ ( k)f(p) $
直观的来看, 这也是一种容斥原理, 哪一项加,哪一项减,哪一项不要,由$ μ (x) $ 控制
至于计算$ μ (x) $, 裆燃不用傻傻的分解质因数, 而是打表(据说这叫线性筛)
放上来我第三个问题的解法吧, 剩下两个有空再补上来
时间复杂度终于降到O(n)了,撒花
1 | import time,os |
