组合数学初步（课堂内容）

组合数学

---

莫比乌斯函数的应用

能量采集 - noi2010

题目描述

栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。
栋栋的植物种得非常整齐，一共有n列，每列有m棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标$(x,y)$来表示，其中x的范围是1至n，表示是在第x列，y的范围是1至m，表示是在第x列的第y棵。
由于能量汇集机器较大，不便移动，栋栋将它放在了一个角上，坐标正好是(0, 0)。 能量汇集机器在汇集的过程中有一定的能量损失。如果一棵植物与能量汇集机器连接而成的线段上有k棵植物，则能量的损失为$2k+1$。例如，当能量汇集机器收集坐标为(2, 4)的植物时，由于连接线段上存在一棵植物(1,2)，会产生3的能量损失。注意，如果一棵植物与能量汇集机器连接的线段上没有植物，则能量损失为1。现在要计算总的能量损失。 下面给出了一个能量采集的例子，其中n = 5，m = 4，一共有20棵植物，在每棵植物上标明了能量汇集机器收集它的能量时产生的能量损失。 在这个例子中，总共产生了36的能量损失。

输入

仅包含一行，为两个整数n和m。

输出

仅包含一个整数，表示总共产生的能量损失。

样例

输入1：

5 4

输出1：

36

输入2：

3 4

输出2：

20

数据范围

对于100%的数据：1 ≤ n, m ≤ 100000。

分析

为了叙述方便，定义$[expression]$为表达式$expression$的值。
首先来看题目要求解的是什么。通过观察可以发现，

$$Ans=\sum_{i=1}^{n}\sum_{j=1}^{m}(gcd(i,j)-1)\times 2$$
也就是
$$Ans=2\times\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)-n\times m$$
问题求解的关键在于得到
$$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)$$
$$\Leftrightarrow \sum_{d=1}^{min(n,m)}d\times \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==d]$$
$$\Leftrightarrow \sum_{d=1}^{min(n,m)}d\times \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}[gcd(i,j)==1]$$
$$\Leftrightarrow \sum_{d=1}^{min(n,m)}d\times \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\sum_{p|gcd(n,m)}\mu (p)$$
$$\Leftrightarrow \sum_{d=1}^{min(n,m)}d\times \sum_{p=1}^{min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\mu (p)\cdot \lfloor \frac{n}{pd} \rfloor \lfloor \frac{m}{pd} \rfloor$$
如果对后面的sigma分块处理，上式可以在$O(n\sqrt{n})$内求出。如果将前面的也一起分块，那么复杂度可以降低到$O(n)$，但是对于本题而言没有太多意义，因为一个是15ms，一个是13ms。CJOJ的O2大法好，只需2ms。

P2394 - 思维的王者

题目描述

思维的王者向wfj2048聊起了最小公倍数(Least Common Multiple)。对于两个正整数a和b，LCM(a, b)表示能同时被a和b整除的最小正整数。例如，LCM(6, 8) = 24。回到家后，wfj2048为了研究最小公倍数，画了一张$N\cdot M$的表格。每个格子里写了一个数字，其中第i行第j列的那个格子里写着数为LCM(i, j)。一个$4\cdot 5$的表格如下：

看着这个表格，wfj2048想到了很多可以思考的问题。不过他最想解决的问题却是一个十分简单的问题：这个表格中所有数的和是多少。当N和M很大时，wfj2048就束手无策了，因此他找到了聪明的你用程序帮他解决这个问题.

Input

第一行为数据组数T（T<=$10^5$）

从第二行开始，对于每组数据，有两个正整数n,m。n，m<=$10^7$

Output

对于每组数据，输出一行答案。 请输出答案mod $10^9$+1的值。

样例

输入：

1
4 5

输出：

122

分析

$$Ans=\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$$
根据定义：
$$Ans=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i\cdot j}{gcd(i,j)}$$
枚举gcd的值：
$$Ans=\sum_{g=1}^{n}\frac{\sum_{i=1}^{n}\sum_{j=1}^{m}i\cdot j\cdot [gcd(i,j)=g]}{g}$$
由于i和j的最大公约数为g，因此可以提出g：
$$Ans=\sum_{g=1}^{n}\frac{g^2\cdot \sum_{i=1}^{\lfloor n/g \rfloor}\sum_{j=1}^{\lfloor m/g \rfloor}i\cdot j\cdot [gcd(i,j)=1]}{g}$$
约分：
$$Ans=\sum_{g=1}^{n}g\cdot \sum_{i=1}^{\lfloor n/g \rfloor}\sum_{j=1}^{\lfloor m/g \rfloor}i\cdot j\cdot [gcd(i,j)=1]$$
把gcd用$\mu$换掉：
$$Ans=\sum_{g=1}^{n}g\cdot \sum_{i=1}^{\lfloor n/g \rfloor}\sum_{j=1}^{\lfloor m/g \rfloor}i\cdot j\cdot \sum_{t|i,t|j}^{\lfloor n/g \rfloor}\mu(t)$$
把$\mu$的枚举提前：
$$Ans=\sum_{g=1}^{n}g\cdot \sum_{t=1}^{\lfloor n/g \rfloor}\mu(t)\sum_{t|i}^{\lfloor n/g \rfloor}\sum_{t|j}^{\lfloor m/g \rfloor}i\cdot j$$
由于t被i和j整除，提出t：
$$Ans=\sum_{g=1}^{n}g\cdot \sum_{t=1}^{\lfloor n/g \rfloor}\mu(t)\cdot t^2\sum_{i=1}^{\lfloor n/gt \rfloor}\sum_{j=1}^{\lfloor m/gt \rfloor}i\cdot j$$
令$S(x)=\sum_{i=1}^{x} i$，则：
$$Ans=\sum_{g=1}^{n}g\cdot \sum_{t=1}^{\lfloor n/g \rfloor}\mu(t)\cdot t^2\cdot S(\lfloor \frac{n}{gt} \rfloor)\cdot S(\lfloor \frac{m}{gt} \rfloor)$$
上面的式子可以在$O(T\cdot nlogn)$内解决。
继续推导：
令$Q=gt$，则：
$$Ans=\sum_{Q=1}^{n}\sum_{t|Q}^{}\frac{Q}{t}\cdot \mu(t)\cdot t^2\cdot S(\lfloor \frac{n}{Q} \rfloor)\cdot S(\lfloor \frac{m}{Q} \rfloor)$$
约分，把只和Q有关的提前：
$$Ans=\sum_{Q=1}^{n}Q\cdot S(\lfloor \frac{n}{Q} \rfloor)\cdot S(\lfloor \frac{m}{Q} \rfloor)\sum_{t|Q}^{}\mu(t)\cdot t$$
注意到S函数可以$O(1)$求解，现在问题转化成如何求$\sum_{t|Q}^{}\mu(t)\cdot t$。令$f(x)=\sum_{t|x}^{}\mu(t)\cdot t$
考虑两个互质的数 $x,y$ ：
$$f(x)\cdot f(y)=(\sum_{t|x} \mu(t)\cdot t)\cdot(\sum_{d|y} \mu(d)\cdot d)$$
暴力乘开：
$$f(x)\cdot f(y)=\sum_{t|x,d|y} \mu(t)\cdot \mu(d)\cdot t\cdot d$$
由于x和y互质，那么x的约数和y的约数均两两互质，因为$\mu$函数是积性函数：
$$f(x)\cdot f(y)=\sum_{t|x,d|y} \mu(td)\cdot t\cdot d$$
令$T=td$，
$$f(x)\cdot f(y)=\sum_{Q|xy} \mu(Q)\cdot Q$$
所以我们发现$f(x)$是一个积性函数，可以使用线性筛法在$O(n)$内解决。
有最后一个问题，线性筛法的过程中，最后会需要计算$f(i\cdot prime_j)$，但$i\%prime_j=0$的一个位置的$f$值。
由于 $prime_j$ 是 $i$ 的一个约数，因此 $prime_j\cdot i$ 所有大于i的约数均有至少一个质因子出现了两次，这就意味着它们的$\mu$值均为0，所以 $f(prime_j\cdot i) = f(i)$。
这样我们就能够在$O(n+T\cdot n)$内解决这个问题，可以获得80%的分数。结合数论分块可以把复杂度降低到$O(n+T\cdot \sqrt{n})$，可以通过全部数据。
值得一提的是，如果你不确定线性筛的时候如何操作，对于大多数题目，带log的筛法能够通过绝大多数的数据。

P2346 - 【SDOI2014】数表

题目描述

有一张N×m的数表，其第i行第j列(1<=i<=n,1<=j<=m)(1<=n,m<=10^5,1<=Q<=2×10^4)的数值为能同时整除i和j的所有自然数之和。
给定a，计算数表中不大于a的数之和。

输入

输入包含多组数据。
输入的第一行一个整数Q表示测试点内的数据组数，接下来Q行，每行三个整数n，m，a(|a| < =10^9)描述一组数据。

输出

对每组数据，输出一行一个整数，表示答案模2^31的值。

样例

输入：

2 
4 4 3 
10 10 5

输出：

20
148

分析

将题目求解的目标明确：

$$Ans=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{\text{k|i && k|j}}k$$
令$f(x)$表示$x$的约数和。通过类似于筛法的方式，我们可以在$O(nlogn)$内计算出$f(1)-f(n)$。
因此，
$$Ans=\sum_{i=1}^{n}\sum_{j=1}^{m}[f(gcd(i,j))\leq a]\cdot f(gcd(i,j))$$
有了上面的经验，我们来进行一些转化。假定$n<m$：
$$Ans=\sum_{d=1}^{n} [f(d)\leq a]\cdot f(d) \sum_{p=1}^{\lfloor \frac{n}{d} \rfloor}\mu(p)\cdot \lfloor \frac{n}{pd} \rfloor \cdot \lfloor \frac{m}{pd} \rfloor$$
令$T=pd$（一个常用的技巧）：
$$Ans=\sum_{T=1}^{n} \sum_{d|T} [f(d)\leq a]\cdot f(d)\cdot \mu(\frac{T}{d})\cdot \lfloor \frac{n}{T} \rfloor \cdot \lfloor \frac{m}{T} \rfloor$$
$$Ans=\sum_{T=1}^{n} \lfloor \frac{n}{T} \rfloor \cdot \lfloor \frac{m}{T} \rfloor \cdot \sum_{d|T} [f(d)\leq a]\cdot f(d)\cdot \mu(\frac{T}{d})$$
对于a确定的情况，我们可以预先求出$\sum_{d|T} [f(d)\leq a]\cdot f(d)\cdot \mu(\frac{T}{d})$的前缀和，配合之前讲解的 数论分块 就可以$O(\sqrt{n})$查询了。
现在问题就在于$a$是由每次询问实时给出的。由于这道题没有强制在线，因此可以把所有的询问预先读取进来，然后按照$a$排序。每次在相应$T$位置插入新增需要加入答案的$f(d)\cdot \mu(\frac{T}{d})$，使用树状数组维护前缀和即可。
假如题目强制在线，那么可以使用主席树提前完成所有插入操作，每次查询对应的版本。注意卡常（反正我没过去）。感兴趣的同学可以在codevs尝试一下。

P2327 - 【NOI2016】循环之美

题目描述

牛牛是一个热爱算法设计的高中生。在他设计的算法中，常常会使用带小数的数进行计算。牛牛认为，如果在 $k$ 进制下，一个数的小数部分是纯循环的，那么它就是美的。

现在，牛牛想知道：对于已知的十进制数 $n$ 和 $m$，在 $k$ 进制下，有多少个数值上互不相等的纯循环小数，可以用分数 $\frac{x}{y}$ 表示,其中 $1\le x \le n, 1 \le y \le m$，且 $x, y$ 是整数。

一个数是纯循环的，当且仅当其可以写成以下形式：

$$a.\dot{c_1} c_2 c_3 \ldots c_{p - 1} \dot{c_p}$$

其中，$a$ 是一个整数，$p\ge 1$；对于 $1 \le i \le p$，$c_i$ 是 $k$ 进制下的一位数字。

例如，在十进制下，$0.45454545 \ldots \ldots = 0.\dot{4}\dot{5}$是纯循环的，它可以用 $\frac{5}{11}$、$\frac{10}{22}$ 等分数表示；在十进制下，$0.1666666\ldots \ldots = 0.1\dot{6}$则不是纯循环的，它可以用 $\frac{1}{6}$ 等分数表示。

需要特别注意的是，我们认为一个整数是纯循环的，因为它的小数部分可以表示成 $0$ 的循环或是 $k - 1$ 的循环；而一个小数部分非 $0$ 的有限小数不是纯循环的。

输入格式

输入文件只有一行，包含三个十进制数 $n, m, k$，意义如题所述。

输出格式

只输出一行一个整数，表示满足条件的美的数的个数。

样例一

input

2 6 10

output

4

explanation

满足条件的数分别是：

$$1/1 = 1.0000 \ldots \ldots$$ $$1/3 = 0.3333 \ldots \ldots$$ $$2/1 = 2.0000 \ldots \ldots$$ $$2/3 = 0.6666 \ldots \ldots$$

$1/1$ 和 $2/2$ 虽然都是纯循环小数，但因为它们相等，因此只计数一次；同样，$1/3$ 和 $2/6$ 也只计数一次。

样例二

input

23333 666666 310

output

5089564081

提示

这部分将提供一个将分数化为对应的小数的方法，如果你已经熟悉这个方法，你不必阅读本提示。

分数可以通过除法，用分子除以分母化为对应的小数。有些分数在除法过程中无法除尽,这样的分数在不断进行的除法过程中余数一定会重复出现。从商数的个位所对应的余数起，设第一次重复出现的余数前两次出现的位置所对应的商数位分别是小数点后第 $a$ 位和小数点后第 $b$ 位（特殊地：如果其中一个对应的商数位是个位，则认为 $a = 0$；不妨设 $a < b$），则其循环部分可以用小数点后第 $a + 1$ 位到小数点后第 $b$ 位的循环来表示。

例如：在十进制下，将 $\frac{5}{11}$ 转化为小数时，个位开始的商数依次为 $4, 5, 4, \ldots$，对应的余数分别为 $6, 5, 6, \ldots$。余数第一次重复出现的位置是个位和小数点后第 $2$ 位,那么 $a = 0, b = 2$ 即其循环部分可以用小数点第 $1$ 位到第 $3$ 位来表示。表示为：$\frac{5}{11} = 0.45454545 \ldots = 0. \dot{4}\dot{5}$。

在十进制下，将 $\frac{1}{6}$ 转化为小数时,个位开始的商数依次为 $1, 6, 6, \ldots$，对应的余数分别为 $4,4,4, \ldots$。余数第一次重复出现的位置是小数点后第 $1$ 位和小数点后第 $2$ 位,即其循环部分可以用小数点后第 $2$ 位来表示。表示为：$\frac{1}{6} = 0.1666 \ldots \ldots = 0.1\dot{6}$。

需要注意的是：商数重复出现并不代表进入了循环节。

限制与约定

对于所有的测试点，保证 $1 \le n \le 10^9, 1 \le m \le 10^9, 2 \le k \le 2000$。对于每个测试点，有以下约束（其中留空的表示没有特殊的约束）：

时间限制：$2\text{s}$

空间限制：$512\text{MB}$

（题目描述来自uoj）

分析

求解目标分析

什么情况下，一个k进制小数会是纯循环小数呢？在10进制下，我们知道3、7、11为分母的小数，只要分子和分母互质，那么就是纯循环小数。可以猜测，当分母和进制互质的时候，只要分子和分母互质，那么就是纯循环小数。编写一个简单的验证程序，发现可以通过大样例。
为什么这样是正确的？
首先假设$x<y$。
还记得我们小学时候做分数化循环小数练习题的经验吗？很多同学都记得，当这一次出现的被除数在之前出现过，那么就意味着出现循环节了。

发现每次的被除数是什么了吗？事实上第c位小数对应的就是$x\cdot k^{c} \text{ }\% y$。如果循环节长度为$l$，那么$x\cdot k^l\equiv x (mod\text{ y})$。
事实上，$x>y$ 的时候，这个结论依旧成立。
将上式左右两边同除x，得到$k^l\equiv 1 (mod\text{ y})$，请数论大神FHR证明$[gcd(k,y)]==1$，我不会证。
由于题目要求不重复，所以还有$[gcd(x,y)]==1$。

推导

令$(a,b)=gcd(a,b)$。
根据上面的分析，可以得到下面的式子：

$$Ans = \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==1\text{ and }gcd(j,k)==1]$$
$$Ans = \sum_{i=1}^{n}\sum_{j=1,(j,k)==1}^{m}\sum_{p|i,p|j}\mu(p)$$
$$Ans = \sum_{j=1,(j,k)==1}^{m}\sum_{i=1}^{n}\sum_{p|i,p|j}\mu(p)$$
由于$p|j$，且$(j,k)==1$，因此$(p,k)==1$。
类似之前的几题，依旧可以转化：
$$Ans = \sum_{p=1,(p,k)==1}^{min(n,m)}\mu(p)\cdot \lfloor \frac{n}{p} \rfloor \sum_{j=1,(j,k)==1,p|j}^{m}1$$
把后面的那个$\sum$枚举的j统统除以p，因为$(p,k)==1$，所以除以p之后的j依旧是和k互质的。由此：
$$Ans = \sum_{p=1,(p,k)==1}^{min(n,m)}\mu(p)\cdot \lfloor \frac{n}{p} \rfloor \sum_{j=1,(j,k)==1}^{\lfloor \frac{m}{p} \rfloor}1$$
使用前缀和优化前后两个$\sum$，可以得到24分。
考虑优化：
令 $$f(x)=\sum_{i=1,(i,k)==1}^{x} 1$$
则
$$f(x)=\lfloor \frac{n}{k} \rfloor \cdot f(k) + f(n\%k)$$
替换掉后面的$\sum$，得到：
$$Ans = \sum_{p=1,(p,k)==1}^{min(n,m)}\mu(p)\cdot \lfloor \frac{n}{p} \rfloor \cdot (\lfloor \frac{m}{pk} \rfloor \cdot f(k) + f(\lfloor \frac{m}{p} \rfloor \% k))$$
只需要预处理出$f(1)$到$f(k)$即可。
可以得到76分。学长写得漂亮可以得到84分。

进一步优化

观察发现效率瓶颈在于求

$$\sum_{d=1,(d,k)==1}^{x}\mu(d)$$
令
$$g(x,k)=\sum_{d=1,(d,k)==1}^{x}\mu(d)$$
取k的一个质因子p，则$k=p^c\cdot q\text{ }((p,q)==1)$，若$(i,k)==1$，则$(i,p)==1$，且$(i,q)==1$。
由容斥原理，
$$\sum_{d=1,(d,k)==1}^{x}\mu(d) = \sum_{d=1,(d,q)==1}^{x}\mu(d)-\sum_{d=1,(d,q)==1,(d,q)!=1}^{x}\mu(d)$$
考虑一个与q互质的的数，那么它一定可以写成$p^xy\text{ }((y,q)==1)$的形式。只有当$x>0$的时候，这个数要被减掉。当$x>1$的时候，$\mu(x)==0$，所以需要考虑的事实上只有$x=1$的情况。枚举每一个可能的$y$值，便可以得到所有需要减掉的x值。
因此：
$$g(x,k)=g(x,q)-\sum_{y=1.(y,q)==1}^{\lfloor \frac{x}{p} \rfloor}\mu(py)$$
当$(p,y)!=1$时，显然$\mu(py)=0$，亦不用考虑，否则$\mu(py)=\mu(p)\cdot \mu(y)$。
故：

所以：

$$g(x,k)=g(x,q)+g(\lfloor \frac{x}{p} \rfloor,k)$$
现在我们得到了一个递推式，可以使用记忆化搜索来实现。由于每次递归要么n会变成$⌊\frac{n}{p}⌋$，有$O(\sqrt{n})$种取值；要么k少了一个质因数，有$ω(k)$种取值，所以总共有$O(ω(k)\sqrt{n})$种取值，计算的复杂度是可以接受的。
当$x=0$时，答案就是0。当$k=1$时，答案是$\sum_{d=1}^{x}\mu(d)$，即莫比乌斯函数的前缀和。
计算莫比乌斯函数前缀和是$O(n)$的，无法通过本题的全部数据。

最后的优化

还是和之前一样，再定义一个函数来解决这个问题。
令

$$du(x)=\sum_{d=1}^{x}\mu(d)$$
根据莫比乌斯函数的性质：
$$\sum_{d|i}^{i}\mu(d)=[i==1]$$
可以得到：
$$\sum_{i=1}^{x}\sum_{d|i}^{i}\mu(d)=1$$
和前面类似：
$$\sum_{i=1}^{x}\sum_{d=1}^{\lfloor \frac{n}{i} \rfloor}\mu(d)=1$$
也就是：
$$\sum_{d=1}^{x}\mu(d)+\sum_{i=2}^{x}\sum_{d=1}^{\lfloor \frac{n}{i} \rfloor}\mu(d)=1$$
移项之后：
$$\sum_{d=1}^{x}\mu(d)=1-\sum_{i=2}^{x}\sum_{d=1}^{\lfloor \frac{n}{i} \rfloor}\mu(d)$$
所以：
$$\sum_{d=1}^{x}\mu(d)=1-\sum_{i=2}^{x}du(\lfloor \frac{n}{i} \rfloor)$$
可以使用数论分块在$O(\sqrt{n})$内求解一层。
为了加速计算，可以提前线性筛预处理出一部分的$du(x)$值，继续展开，可以证明这样做的复杂度为$O(n^{\frac{2}{3}})$（我不会证）。
记忆化搜索求解$du(x)$，便可解决这个问题。