Luogu4619 [SDOI2018] 旧试题

• 参考资料：《数论选讲》in APIO2024 by zhoukangyang.（多元积性函数）

讲义里提到本题的 做法，但没有细说。我将详细地陈述此做法。

• Notations： 为 的上界；记前缀和 。

基本概念

• 多元积性函数

  函数 满足当 时，有 ，则称 为（三元）积性函数。

• Observation：令 ，则 是积性函数。问题转化为三元积性函数的矩阵和。

• 积性分解

  将 分解为 ，，，对于积性函数

• 狄利克雷卷积

  三元积性函数的狄利克雷卷积定义为 类似一元的情况，有如下性质成立：

  • 积性函数的卷积是积性函数。
  • 积性函数的逆是积性函数。

• 贝尔级数

  在素数 处观测积性函数 ，定义贝尔级数为三元形式幂级数 类似一元的情况，两个函数卷积，对应的贝尔级数相乘。

低阶拟合法

模仿 Powerful Number 的思路，构造一个数论函数 使得 在素数幂次较低时相等，然后做除法 ， 的非零元素有希望较少。

计算 的矩阵和时 如果 稀疏，且 的矩阵和易求，我们就得到了一个不错的算法。

一个自然的想法是，构造 ，则

• 容易计算。

  预处理 后容易 计算。

• 和 在低阶处相等。

  可以发现 ，，。

  为了更直观地说明这一点，构造贝尔级数。 和 的系数在“三条棱”上是相等的，根据幂级数逆元的知识，可以发现 在这三条棱上都是 ，没有更多的项。即是说： 不仅如此，计算发现： 除了上述项，其余都是零。

• 密度的分析

  枚举量就是 的非零项数量，将条件放宽为 ，。

  记 为满足 的非零 个数，则复杂度为 。

  可以证明 是积性函数，且 ，。

  • Lemma: 对于数论函数 ，找出最小的 满足 。记 为 的最大值，其余 ，则 。

  根据这个引理，可以得到 ，对应复杂度 。

  此界太过宽松，这是因为我们将矩形区域粗暴地放缩成了双曲区域 ，两者的面积比就是 。为了去除多余的 log 因子，必须考虑为矩形区域。

  定义三元数论函数 ，我们的目标是估计 的矩阵和。

  令 满足 ，其余都是 ，。显然，。

  先考察 的矩阵和， 总是可以写作 ，枚举 进行计数： 用讨论将 拆掉， 较小的部分是 根据对称性，另一部分是 。

  其中 ，这是一个经典形式 解得 。代入得 。

  考虑 的矩阵和 记 为满足 的非零 个数。 的全零前缀更长，根据引理， 在 的非零个数不超过 ，密度可以估计为 。枚举 ，复杂度可以估计为 综上，我们证明了枚举量是 。