数论学习入门 #1

数论虽然在 NOIP 中不作深入的要求，但是在这之上的比赛就经常会有涉及到这类知识的算法题目。

本文来总结整理一下一些初等的数论知识。

Mathematics is the queen of the sciences—and number theory is the queen of mathematics. 数学是科学的皇后，数论是数学的皇后。

——卡尔·弗里德里希·高斯

基本定理和性质

本文所使用的符号均参照数学选修 4-6

质数与合数

在大于 的自然数中，除了 和该数自身外，无法被其他自然数整除的数称为质数（aka. 素数)。

大于 的自然数若不是素数，则称之为合数（aka. 合成数）。

既不是质数，也不是合数。

最大公约数和最小公倍数

最大公约数（abbr. gcd, greatest common divisor）指能够整除多个整数的最大正整数。

如果 是 和 的最大公约数，我们记为 。

如果 ，那么我们称 与 互质，可以记为 。

最小公倍数（abbr. lcm, least common multiple）指能够被多个整数整除的最小正整数。

如果 是 和 的最大公约数，我们记为 。

一个大家都知道的结论：

整除

如果 能够整除 ，我们称 是 的约数或因子，记为 。

相反，如果 不能够整除 ，我们记为 。

整除有一些优秀的性质：

• 或

正确性显然。

Sum 和 Product

算数基本定理

设 ，则 可以分解成素数的乘积

如果不计这些素数的次序，则分解式是唯一的。

设 是 的标准分解式，若用 表示 的所有正约数的个数，那么

组合数与阶乘

组合数（aka. 二项式系数） 表示从 个本质不同的物品中选出 个物品的方案数（不计选择的顺序）。

其中

于是我们有递推式：

二项式定理：

同余

如果 和 对 的余数相等，那么我们记为

数论函数

积性函数

如果 是积性函数，那么对于 ，满足 。

下面是一些常见的积性函数：

• 表示 的正因子个数
• 表示 的所有正因子的和

欧拉函数

欧拉函数 表示小于 的与 互质的正整数的个数。

设 ，则有

是积性函数。

欧拉定理：设 ，，则

如果 是质数，那么 ，这其实就是费马小定理了。

费马小定理：设 是质数，，则

扩展欧拉定理：

例题： 求

解： 令 则 于是问题可以转化为求 对 取模的子问题。 以此类推，当模数为 时，答案显然为 。 然后递归回去计算即可。

莫比乌斯函数

莫比乌斯函数 的定义：

设 ，

也是积性函数。

算法

狄利克雷卷积

如果 是数论函数，令 ，则

狄利克雷卷积有一些优秀的性质：

• 交换律
• 结合律
• 分配律
• 单位元

一些公式：

莫比乌斯反演

如果 是数论函数，则有

证明：

变形：

这怎么证啊。。。

例题： 求

解： 设

则有

根据莫比乌斯反演得

考虑如何计算 ，我们马上就能发现

所以

直接计算是 的，可以利用前缀和和分块的技巧优化到单次询问 。

总结

如果你不知道一个公式怎么证明，那就打表打表找规律大法好

文章写太长不好，剩下来的以后讲。 下次应该会多写几道例题。

别问我为什么退役了才写这个