数论进阶-Preknowledge 参考资料：洛谷网校2018夏季省选基础班SX-3数论进阶课程及课件 一、整除与取整除法 1.1 定义 1、整除
\(\forall~x,y~\in~Z^+,\) 若 \(\exists~k~~,~~s.t.~y~=~kx\)，则称 \(y\) 是 \(x\) 的倍数，\(x\) 整除 \(y\)。记做 \(x~|~y\)
2、取整\(\forall~x~\in~Q\)，\(\lfloor x \rfloor\) 代表不大于 \(x\) 的最大整数，\(\lceil x \rceil\) 代表不小于 \(x\) 的最大整数。
3、取整除法\(\forall~x,y~\in~Z\)，\(\left \lfloor \frac{y}{x} \right \rfloor\) 代表 \(y\) 关于 \(x\) 的带余除法表达式中 \(x\) 一项的系数
1.2 性质 1、取整除法引理 \((1.2.1)\)\(\forall~x,y~\in~Z\)，\(\left \lfloor \frac{y}{x} \right \rfloor~\times~x~\leq~y\)
证明：根据取整除法的定义易得
\[\left\lfloor \frac{y}{x} \right\rfloor~\leq~\frac{y}{x}\]
等式两侧同乘 \(x\) 得
\(\left\lfloor \frac{y}{x} \right\rfloor~\times~x~\leq~\frac{y}{x}~\times~x~=~y\)
证毕 2、倍数个数定理 \((1.2.2)\)\(\forall~n,d~\in~Z^+\)，在 \([1,n]\) 中，共有 \(\left \lfloor \frac{n}{d} \right \rfloor\) 个数是 \(d\) 的倍数
证明：将 \(d\) 的倍数从小到大排序，分别为 \(x_1~,~x_2~,\dots~x_k\)，则显然 \(x_i~=~i~\times~d\)。于是其中最大的数字 \(x_k~=~k~\times~d\)。
若 \(k~<~\left \lfloor \frac{n}{d} \right \rfloor\)，设 \(k'~=~\left\lfloor \frac{d}{n} \right \rfloor\) 根据引理 \(1.2.1\)，\(d~\times~k'~\leq~n\) 且 \(k~\times~d~<~k'~\times~d\)，这与 \(x_k\) 是最大的数字矛盾
若 \(k~>~\left \lfloor \frac{n}{d} \right \rfloor\)，根据引理 \(1.2.1\)，\(d~\times~k~>~n\)，不合要求
于是 \(k~=~\left \lfloor \frac{n}{d} \right \rfloor\)。
证毕 3、商的个数定理 \((1.2.3)\)\(\forall~n~\in~Z^+\)，则 \(d~\in~[1,n]\) 时 \(\left \lfloor \frac{n}{d} \right \rfloor\) 的取值共有 \(O(\sqrt{n})\) 种
证明：分两种情况，当 \(d~\leq~\sqrt{n}\) 时，\(d\) 共有 \(O(\sqrt{n})\) 种取值
因为对于 \(n\) 的一个因数 \(x\)，必然能找到一个数 \(y\) 使得 \(x~\times~y~=~n\)，这样的 \(x,y\) 是一一对应的，故而对于每个大于 \(\sqrt{n}\) 的因数 \(x\)，必然存在一个 \(y~,s.t.~~x~\times~y~=~n\)。
因为 \(y~>~\sqrt{n}\)，所以 \(x~<~\sqrt{n}\)。这样的 \(x\) 共有 \(O(\sqrt{n})\) 种，由一一对应关系， \(y\) 也有 \(O(\sqrt{n})\) 种。于是总的取值共有 \(O(\sqrt{n})\) 种。
证毕 4、例题 Description给出一个 \(n\)，求 \(\sum_{i=1}^{n}~\left \lfloor \frac{n}{i} \right \rfloor\)。\(n~\leq~10^{12}\)
Solution既然商只有 \(O(\sqrt{n})\) 个，于是考虑直接枚举商。考虑枚举商等价于对每个商 \(j\) 枚举每一个最小的 \(i\) 使得 \(j~=~\left \lfloor \frac{n}{i} \right \rfloor\)。考虑最大的满足上式的 \(k\)，则 \(k~=~\left \lfloor \frac{n}{j} \right \rfloor\)。将在下方给出证明。则商为 \(j\) 时最答案的贡献是 \((k~-~i~+~1)~\times~j\)。最小的 \(i\) 显然为 \(1\)，如果求出了最大的 \(k\)，则对应下一个商的 \(i\) 显然为 \(k~+~1\)。根据定理 \(1.2.3\)，时间复杂度 \(O(\sqrt{n})\)。
下面证明最大的 \(k\) 使得 \(j~=~\left \lfloor \frac{n}{k} \right \rfloor\) 的值为 \(\left \lfloor \frac{n}{j} \right \rfloor\)：
考虑当 \(k~,~j~\in~Q\) 时，\(j~=~\frac{n}{k}\) 的图像是一个反比例函数。当等号右侧改成取整后，相当于所有的 \(j\) 都向下移到了最靠近的纵坐标为整数的点上。于是 \(k~\times~j~\leq~n\)。则 \(k~\leq~\left \lfloor \frac{n}{j} \right \rfloor\)。最大的 \(k\) 显然是 \(\left \lfloor \frac{n}{j} \right \rfloor\)
证毕。
二、同余 2.1 定义\(\forall~x,y,p~\in~Z^+\)， 若 \(x~\bmod~p~=~y~\bmod~p\)，则称 \(x,y\) 在 模 \(p\) 域下同余，记为 \(x~\equiv~y~\pmod p\)
2.2 性质同余式支持同余号两侧同加、减、乘。同时具有对称性，自反性，传递性。
\(x~\equiv~y~\pmod p\) 的另一表达是 \(p~|~(x-y)\)。(不妨设\(x~\geq~y\))
三、剩余系 3.1 完全剩余系对于一个正整数 \(n\)，模 \(n\) 意义下的完全剩余系为正整数集全体对 \(n\) 取模的结果的集合，记为 \(Z_n\)
一般的，\(Z_n~=~\{0~,~1~,~2~,~\dots~,n~-~1\}\)
3.2 简化剩余系