间接计数条件
给定正整数 ,每项不超过 ,有多少无序的不同下标配对 满足 ?数值可以重复;不同下标仍构成一对。逐对测试是直接的方法,但因数计数可以在许多配对之间重用信息。
定义 6.1.1
(Möbius 函数)
Möbius 函数定义在正整数上:;若某个素数的平方整除 ,则 ;否则若 是 个不同素数的乘积,则 。
以下结果假设素因数分解唯一。
因数指示式
定理 6.1.2
(Möbius 函数的因数和)
对正整数 ,
因此,对正整数 ,有 。
证明
(因数对应素因数的子集)
若 ,唯一的因数是一,而 。否则设其不同素因数为 ,其中 。含平方因子的因数贡献为零;其余每个因数都是 中若干个不同素数的乘积,因此对应这些素数的一个子集 ,贡献 。所以其和为
至于推论, 与 的公因数恰好是 的因数。把恒等式用于 :当 时得 ,否则得 。
证明透视
为何只有 g 等于一时和才是一
唯一不平凡的步骤,是舍去所有含平方因子的因数,并把其余因数按 的素因数子集编号;这一步用到唯一分解。二项展开 只在 时为零; 时同一式子是空积 ,正好就是 的情形,所以恒等式的两种情形其实是同一个计算。非无平方因子的因数权重取 是关键:没有它, 的所有因数之和就不再抵消。
令 为满足 的下标 的个数。
定理 6.1.3
(用 Möbius 和表示互素配对数)
设 ,且所有 ,则
证明
(交换两个有限和)
对每一对代入因数指示式,再交换求和顺序:
右边所数的集合,是从 个被 整除的下标中选出的不同下标对,所以大小为 。某个 的因数至多为 ,而 时 ,所以求和可以在 处停止。
二项式系数计算的是下标对,不是不同数值的配对;当 时它为零。负项是容斥修正,最终的计数非负。
反例模式
素数平方会改变权重
若只按素因数总个数给每个因数加正负号,就会出错。对 ,正确的值是 、、。若误设 ,其和变成 而不是 ,错误地把最大公因数 当成一。
小例子
例题 6.1.4
(五个数的例子)
对 ,有 、(即 )、(即 )。其余每个 至多整除一项,所以公式给出
四个下标对对应数值 、、 和 。逐一检查全部十对可以验证:其余六对的最大公因数依次为 。
例题 6.1.5
(相等的数没有互素配对)
设 。则 、,而 时 。公式给出 ,这正是应有的结果:每一对的最大公因数都是 。重复的数值按下标计算,两项恰好抵消。
计算各项数量
令 为等于 的输入个数。对每个 ,把 相加求出 。Möbius 值也可以由因数恒等式得到,不必对每个输入分解素因数:
mu[1] = 1; mu[2..M] = 0
for d = 1..M:
for multiple = 2d, 3d, ... while multiple <= M:
mu[multiple] -= mu[d]
命题 6.1.6
(该筛法计算 Möbius 值)
外层循环到达下标 时,;因此结束时,对所有 都有 。
证明
(对下标作强归纳)
时尚未减去任何值,。设 ,并假设循环到达每个 时 。 从 开始,对每个满足 、 的 (即 的每个真因数 )恰好被减去一次 。因此到达下标 时它等于 。由因数恒等式(取 )有 ,所以这个值等于 。之后的迭代只会修改各自下标之后的项。
两个倍数循环各至多访问 个位置。计入输入频数以及最后的求和,时间为 ,额外空间为 ,假设整数运算精确且为常数时间。计数可能超出定长整数的范围,所以实现时必须选取足够的表示。这个界取决于最大值 ,而不只取决于输入的个数。
例题 6.1.7
(M 等于 6 时的筛法)
从 (下标 )开始。下标 从下标 各减去 :。下标 从下标 和 减去 :。下标 从下标 减去 :。下标 在 以内没有自身以外的倍数。结果 与定义一致;特别是 和 。
常见错误
(用不同数值代替下标来计数)
对 ,互素的下标对有两个,即 和 ,但互素的不同数值配对只有一个。公式给出 ,计算的是下标。先去重再计算,回答的是另一个问题。
常见错误
(把成本只看作输入长度的函数)
该筛法分配并扫描长度为 的表。当 而 时,输入很小,但范围 使表的大小,以及运行时间和内存都很大。
习题与解答
快速检查
( 是多少?)
先分解 。
解答 · 答案
,因为 整除 。
快速检查
( 是多少?)
是否无平方因子?
解答 · 答案
,因为 是两个不同素数的乘积。
快速检查
(对两项 ,有多少个互素下标对?)
按下标对计算,不按不同数值计算。
解答 · 答案
一对:唯一的配对是 ,其最大公因数为一。公式一致:,所以和为 。
快速检查
(若输入很少却含有极大的数值,为什么所述筛法未必高效?)
哪个参数决定表的大小?
解答 · 答案
时间及额外内存取决于 ; 小本身并不意味着分配的范围小。
快速检查
(用公式计算 中互素下标对的个数。)
计算 和 ,并检查 是否成立。
解答 · 答案
、(即 )、、。计数为 。直接检查:,而 ,所以有两对。