202404
0 前言
离散数学是本书的重点，而整数又是离散数学的中心议题。数论 是讨论整数性质的重要数学分支，因此我们要来探索它。
——《具体数学》第四章
标有 * 的为拓展内容，或者说比较难的题目，但它们都非常有趣。
部分题目的代码是洛谷的提交记录，阅读这篇文章的大多数同学都该能看（若有需要可以找我要）。
没看懂的地方直接问，不排除我会存在手误。
1 基本概念
1.1 整除
两个整数相除，我们自然想去讨论商是否是一个整数。小学生常常期待这个，因为整数比分数写起来好看。
这引出了数论中的基础概念：整除。
如果 \(m \gt 0\) 且 \(n /m\) 是一个整数，我们就说 \(m\) 整除 \(n\)（或者 \(n\) 被 \(m\) 整除）。这个性质奠定了整个数论的基础，所以我们赋予它一个特殊的记号会更方便，记为
\[m \mid n \Leftrightarrow m \gt 0 且对于某个整数 k 有 n=mk \]同样的，如果 \(m\) 不整除 \(n\)，我们就写成 \(m \nmid n\)。
1.2 整值函数
整数是离散数学的支柱，我们常常需要将分数或者任意的实数转换到整数。 ——《具体数学》第三章
我们首先来讨论 底（floor，最大整数）函数和 顶（ceiling，最小整数）函数，对于所有实数 \(x\)，其定义如下：
\[\begin{aligned} \lfloor x \rfloor & = 小于或者等于 x 的最大整数 \\ \lceil x \rceil & = 大于或者等于 x 的最小整数 \end{aligned} \]俗称 下取整 和 上取整，底和顶也会在数论中有许多应用，在后续的部分内容中我们也会用到。
\(x\) 和 \(\lfloor x \rfloor\) 之间的差称之为 \(x\) 的 分数部分，它在应用中经常出现，所以也值得拥有自己的记号：
\[\{ x\} =x - \lfloor x \rfloor \]我们有时称 \(\lfloor x \rfloor\) 是 \(x\) 的 整数部分，因为 \(x= \lfloor x \rfloor + \{ x\}\)，这也是一个实数的表示方法。
尝试在这里就证明一个非常有趣且有用的事实：如果 \(m\) 和 \(n\) 是整数且分母 \(n\) 为正，则
\[\left \lfloor \frac{x+m} n \right \rfloor = \left \lfloor \frac {\left \lfloor x \right \rfloor +m} n\right \rfloor 且 \left \lceil \frac {x+m} n \right \rceil = \left \lceil \frac{\left \lceil x \right \rceil + m} n \right \rceil \]设 \(f(x)\) 是任意一个具有如下性质且在一个实数区间连续的单调递增函数
\[f(x) = 整数 \Rightarrow x = 整数 \]于是只要 \(f(x),f(\left \lceil x \right \rceil),f(\left \lfloor x \right \rfloor)\) 有定义，我们就有
\[\left \lfloor f(x) \right \rfloor = \left \lfloor f( \left \lfloor x \right \rfloor)\right \rfloor 和 \left \lceil f(x) \right \rceil = \left \lceil f( \left \lceil x \right \rceil) \right \rceil \]画出图来容易发现这是显然的，这里不做证明。
我们发现其实 \(f(x)=\frac {x+m} n\) 也具有上面要求的 \(f(x)\) 的性质，于是我们就证得了上面的结论。
1.3 带余除法
当 \(m\) 和 \(n\) 是正整数时，\(n\) 被 \(m\) 除的商是 \(\lfloor n/m \rfloor\)。而大多数情况我们都不能做到 \(m\) 整除 \(n\)，所以这个除法的余数也有一个简单的记号，很方便，我们称它是 \(n \bmod m\)。基本公式
\[n = m \lfloor n/m \rfloor + n \bmod m \]告诉我们，可以将 \(n \bmod m\) 表示成 \(n - m \lfloor n/m \rfloor\)，我们可以将它推广到任意实数：
\[x \bmod y = x- y \lfloor x/y \rfloor,y \neq 0 \]\(y=0\) 呢？为了避免用 \(0\) 作除数，也为了完整起见，我们可以定义：
\[x \bmod 0 = x \]这里的 \(\text{mod}\) 就被定义成了一个二元运算，也就是 取模。容易发现 \(x \bmod y\) 是在 \([0,y-1]\) 中的一个值。
我们约定 \(\text{mod}\) 比加法或者减法的优先级高。同时，分配率 是 \(\text{mod}\) 最重要的代数性质，对于所有实数 \(c,x,y\)，我们有
\[c ( x \bmod y) = (cx) \bmod (cy) \]容易从定义证明这个法则，因为如果 \(cy \neq 0\)，则有
\[c ( x \bmod y) = c(x-y\lfloor x/y \rfloor) = cx - cy \lfloor cx/cy \rfloor = cx \bmod cy \]且模数为零时该式显然也为真（两边都是 \(cx\)）。
关于 \(\text{mod}\)，还有一些非常显然的性质。
- \((a+b) \bmod p = ((a \bmod p) + (b \bmod p)) \bmod p\)。
- \((ab) \bmod p= ((a \bmod p)(b \bmod p)) \bmod p\)。
- \(a \bmod bk \bmod b = a \bmod b\)。
前两条定义了 \(\text{mod}\) 的加法和乘法，第三条则是关于模数的一个转化。
这些性质都是耳熟能详的，这里也不做证明。
1.4 同余关系
模运算是数论提供的一种重要工具，我们在上面把它当成二元运算使用，而在这里我们也可以把 \(\text{mod}\) 运用到整个方程上面，为此，我们使用稍不同的记号会更加方便：
\[a \equiv b \pmod m \Longleftrightarrow a \bmod m = b \bmod m \]由于 \(x \bmod m\) 与 \(x\) 相差 \(m\) 的倍数，因而我们可以用另一种方式来解读同余式：
\[a \equiv b \pmod m \Leftrightarrow a-b 是 m 的倍数 \]同余符号 \(\equiv\) 看起来很像 \(=\)，因为同余式与方程非常相像。例如，我们将同余式元素相加减，仍保持同余关系：
\[a \equiv b \quad 且 \quad c \equiv d \quad \Rightarrow \quad a \pm c \equiv b \pm d \pmod m \]乘法同样有效，只要处理的对象是整数：
\[a \equiv b \quad 且 \quad c \equiv d \quad \Rightarrow \quad ac \equiv bd \pmod m \]证明直接作差：\(ac-bd=(a-b)c+b(c-d)\)。反复利用乘法性质，我们可以取幂：
\[a \equiv b \quad \Rightarrow \quad a^n \equiv b^n \pmod m,a,b 是整数,整数 n \ge 0 \]这样一来，我们对方程所习惯做的大多数代数运算对同余式都可以运用，但并不是所有运算。除法运算显然不在其中。
以下部分可能会用到之后要讲的内容。
如果 \(ad \equiv bd \pmod m\)，我们不能总断言 \(a \equiv b \pmod m\)。例如 \(3 \times 2 \equiv 5 \times 2 \pmod 4\)，但 \(3 \not \equiv 5 \pmod 4\)。
然而在 \(d\) 与 \(m\) 互素的情形中，我们可以挽救这一消元的性质：
\[ad \equiv bd \pmod m \quad \Longleftrightarrow a \equiv b \pmod m ,a,b,d,m 是整数,d \bot m \]它的证明是直接在式子两边乘上 \(d\) 的逆元，进而，我们可以把这个东西推广到更为一般的法则，它尽可能小地改变模：
\[ad \equiv bd \pmod m \quad \Longrightarrow \quad a \equiv b \pmod {\frac m {\gcd(d,m)}} \]进一步观察改变模的想法，我们可以得到另外一些式子：
\[a \equiv b \pmod {md} \Longrightarrow a \equiv b \pmod m \]反过来，如果我们知道对于两个小的模数有 \(a \equiv b\)，是否能断定对于一个更大的模数有 \(a \equiv b\) 呢？这个规则是
\[a \equiv b \pmod m 且 a \equiv b \pmod n \Longleftrightarrow a \equiv b \pmod {\operatorname{lcm}(a,b)} \]注意关注这个式子的特殊情形 \(m \bot n\)，这在之后的 中国剩余定理 颇有应用。
2 欧几里得
有着我们熟悉的 \(\gcd(a,b)\) 和 \(\operatorname{lcm}(a,b)\)。
2.1 欧几里得算法（gcd）
欧几里得算法，又称辗转相除法，常用与递归得到最大公因数。
\[\gcd(a,b) = \gcd(b,a \bmod b) \]而这是容易简单证明的：
设 \(a=kb+r\)，\(a,b\) 的最大公因数为 \(d\)，那么一定满足 \(d|a,d|b\)。
于是 \(r= a-kb\)，我们将两边同时 \(\div d\) 就可以得到 \(\frac r d =\frac a d - \frac{kb} d\)。
由于 \(d|a,d|b\)，所以上面式子的右边一定是整数，于是 \(\frac r d\) 也是一个整数。
这样一来，\(d\) 也是 \(a \bmod b = r\) 的因数，得证。
CF1806F2 GCD Master (hard version)
给定 \(n, m\) 和一个长度为 \(n\) 的序列 \(\{a_i\} (a_i\leq m)\)。
定义一次对一个长度为 \(m\) 的序列的操作为，选择序列中两个下标 \(1\leq i < j \leq m\)，删去 \(a_i\) 与 \(a_j\)，然后在序列末端加入 \(\gcd(a_i, a_j)\)。
例如，对于 \([7, 6, 2]\)，一次操作可以选择下标 \(2\) 与 \(3\)，这样操作后，序列变成 \([7, 2]\)。
给定 \(k\)，求对序列 \(\{a_i\}\) 执行 \(k\) 次操作后得到序列中的数的和的最大值。
\(1 \le K \lt n \le 10^6,1 \le m \le 10^{18}\)。
感谢
标签：lfloor,right,frac,Theory,bmod,Number,rfloor,left From： https://www.cnblogs.com/H-W-Y/p/18203501/NumberTheory1