整数的离散性
tangtianyao0123
·
·
算法·理论
前言
这是我和盟友两位五年级蒟蒻合作的数论合集第一篇文章，大佬们不喜勿喷，感谢您的收看。
不等式整数解
一个集合离散是指集合中任意两个不同的数之间的距离会有一个大于零的下界，请判断整数集、实数集、有理数集、自然数集是否离散。
- 整数集和自然数集中任意两个不同的数之间的距离都大于等于一，故离散。
- 实数集和有理数集中任意两个不同的数之间都会存在一个新的实数（有理数），所以两个不同的实数（有理数）之间的距离是没有大于零的下界的，故不离散，故稠密。
那么在任意一个有限的范围中，整数的个数是有限的，所以找到未知数的范围再逐一验证就一定能找到解。
离散的集合可以将集合中的所有数从小到大一个接一个地排成一排，那么相邻两个数之间不存在别的数属于该集合。如果一个元素在相邻两个集合中的数之间时，则它不属于该集合，证明整数和完全平方数时可以使用这种方法，被称为“卡范围”。
例题一
::::info[题目]{open}
一个正整数的立方为四位数，四次方为六位数，且用到的十个数字互不相同，求这个数。
::::
将它设出来后，可得到关于四位数与六位数的不等式，得到未知数 n 的范围 18 \le n \le 21，根据末尾判断 n = 18, 19，逐一枚举即可。
::::success[完整解答]{open}
设这个数为 n，由题意
1000 \le n^3 \le 9999 < 100000 \le n^4 \le 999999
解得
18 \le n \le 21
又
20^3 \equiv 20^4 \equiv 0 \pmod{10}
21^3 \equiv 21^4 \equiv 1 \pmod{10}
\therefore n = 18, 19
经枚举，n = 18。
::::
如果你知道整除特征，你就能一眼看出 n = 19 不行，读者可以自行学习。
例题二
::::info[题目]{open}
求使不等式 \frac{9}{17} < \frac{n}{n + k} < \frac{8}{15} 对唯一整数 k 成立的最大整数 n。
::::
取倒后，可以得到 \frac{7}{8}n < k < \frac{8}{9}n，得到不等式 (\frac{8}{9} - \frac{7}{8})n \le 2，得到 n \le 144，代入检验即可。
::::success[完整解答]{open}
\because \frac{9}{17} < \frac{n}{n + k} < \frac{8}{15}
\therefore \frac{17}{9} > \frac{n + k}{n} > \frac{15}{8}
\therefore \frac{8}{9} > \frac{k}{n} > \frac{7}{8}
\therefore \frac{7}{8}n < k < \frac{8}{9}n
\therefore \left( \frac{8}{9} - \frac{7}{8} \right)n \le 2
\therefore n \le 144
此时
128 > k > 126
\therefore k = 127
\therefore n_{\max} = 144
::::
多元对称有序枚举
在多元对称有序枚举时，可以将未知数排序，从小到大（从大到小）进行枚举，每次枚举时，可以稍微卡一下最大数（最小数）的范围，来保证有限枚举。
例题一
::::info[题目]{open}
求方程 \frac{1}{a} + \frac{1}{b} + \frac{1}{c} = \frac{1}{2} 的正整数解数量。
::::
由于原式是对称式，那么不妨设 a \le b \le c，易知 \frac{1}{a} < \frac{1}{2} \le \frac{3}{a}，得 3 \le a \le 6，枚举 a 得到 \frac{1}{b} + \frac{1}{c} = \frac{x}{y}，两边同乘 ybc 后因式分解求解即可。
::::success[完整解答]{open}
不妨设
a \le b \le c
易知
\frac{1}{a} < \frac{1}{2} \le \frac{3}{a}
\therefore 3 \le a \le 6
若 a = 3
\therefore \frac{1}{b} + \frac{1}{c} = \frac{1}{6}
\therefore bc - 6b - 6c = 0
\therefore (b - 6)(c - 6) = 36
\therefore \begin{cases}
a = 3, 3, 3, 3, 3 \\
b = 7, 8, 9, 10, 12 \\
c = 42, 24, 18, 15, 12
\end{cases}
若 a = 4
\therefore \frac{1}{b} + \frac{1}{c} = \frac{1}{4}
\therefore bc - 4b - 4c = 0
\therefore (b - 4)(c - 4) = 16
\therefore \begin{cases} a = 4, 4, 4 \\
b = 5, 6, 8 \\
c = 20, 12, 8
\end{cases}
若 a = 5
\therefore \frac{1}{b} + \frac{1}{c} = \frac{3}{10}
\therefore 9bc - 30b - 30c = 0
\therefore (3b - 10)(3c - 10) = 100
\therefore \begin{cases}
a = 5 \\
b = 5 \\
c = 10
\end{cases}
若 a = 6
\therefore \frac{1}{b} + \frac{1}{c} = \frac{1}{3}
bc - 3b - 3c = 0
\therefore (b - 3)(c - 3) = 9
\therefore \begin{cases}
a = 6 \\
b = 6 \\
c = 6
\end{cases}
综上，共 6 \times 6 + 3 \times 3 + 1 = 46 组。
::::
例题二
当上题中的三个数变为四个数时，枚举量会增加不少；如果 \frac{1}{2} 变成让你求的几个数，你还会这么有耐心的枚举吗？
::::info[题目]{open}
（2007，白俄罗斯数学奥林匹克）求所有的正整数 n，使它能整除它的不同的四个因数之和。
::::
建议先阅读第五讲整除的定义与性质。
如果这四个因数为 a_1, a_2, a_3, a_4，那么不方便体现四个因数与 n 的关系，在枚举因数时消不掉 n，所以设四个因数为 \frac{n}{a_1}, \frac{n}{a_2}, \frac{n}{a_3}, \frac{n}{a_4} 在枚举时就消掉了 n，所以问题就变成了 \frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3} + \frac{1}{a_4} = k \in \Z^{+}。简单放缩得 k = 1, 2，然后逐一枚举即可。
::::success[完整解答]{open}
设 n 的四个因数为 \frac{n}{a_1}, \frac{n}{a_2}, \frac{n}{a_3}, \frac{n}{a_4}，
其中 a_1, a_2, a_3, a_4 \in \Z^{+}, a_1 < a_2 < a_3 < a_4，且 a_1, a_2, a_3, a_4 \mid n。
\therefore [a_1, a_2, a_3, a_4] \mid n
由题意
n \mid \frac{n}{a_1} + \frac{n}{a_2} + \frac{n}{a_3} + \frac{n}{a_4}
\therefore \frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3} + \frac{1}{a_4} \in \Z^{+}
设
\frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3} + \frac{1}{a_4} = k \in \Z^{+}
\frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3} + \frac{1}{a_4} = k \le 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} < 3
\therefore k = 1, 2
若 k = 1
\therefore \frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3} + \frac{1}{a_4} = 1
\therefore \frac{1}{a_1} < 1 < \frac{4}{a_1}
\therefore a_1 = 2, 3
若 a_1 = 2
由例题一的解，6 \mid n 或 20 \mid n。
若 a_1 = 3
\frac{1}{a_2} + \frac{1}{a_3} + \frac{1}{a_4} = \frac{2}{3}
（省略枚举过程，毕竟简单，跟上一题一样。）
解得 6 \mid n 或 20 \mid n。
若 k = 2
若 a_3 \le 4，则 \text{LHS} \le 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{5} < 1 = \text{RHS}，矛盾。
\therefore a_1 = 1, a_2 = 2, a_3 = 3, a_4 = 6
\therefore 6 \mid n
综上，6 \mid n 或 20 \mid n。
::::
乘方问题中的范围分析
如果一个代数式是完全平方数（高次方同理），可以将它夹在两个完全平方数中间，使得这个数的范围有限。再逐一解方程即可。
例题一
::::info[题目]{open}
求所有正整数 n 使得 n^2 + 5n + 1 为完全平方数。
::::
通过刚才的知识点，我们可以将 n^2 + 5n + 1 夹在 n^2 和 n^2 + 6n + 9 = (n + 3)^2 中间，所以 n^2 + 5n + 1 = n^2 + 4n + 4 解方程即可。
::::success[完整解答]{open}
\because n^2 \le n^2 + 5n + 1 \le n^2 + 6n + 9 = (n + 3)^2
又 n^2 + 5n + 1 为完全平方数。
\therefore n^2 + 5n + 1 = (n + 2)^2 = n^2 + 4n + 4
\therefore n = 3
::::
例题二
::::info[题目]{open}
求使得 4^{27} + 4^{1000} + 4^x 为完全平方数的最大整数 x。
::::
当 x \ge 27 时，4^{x-27} + 4^{973} + 1 为完全平方数，又 4^{x-27} + 4^{973} + 1 > 4^{x-27} = (2^{x-27})^2，得到 4^{x-27} + 4^{973} + 1 \le (2^{x-27} + 1)^2，解出 x \le 1972。
::::success[完整解答]{open}
若 x \ge 27。
\therefore 4^{x-27} + 4^{973} + 1 \text{ 为完全平方数。}
\because 4^{x-27} + 4^{973} + 1 > 4^{x-27} = (2^{x-27})^2
\therefore 4^{x-27} + 4^{973} + 1 \ge (2^{x-27} + 1)^2 = 4^{x-27} + 2^{x-26} + 1
\therefore 2^{1946} \ge 2^{x-26}
\therefore 1946 \ge x - 26
\therefore x \le 1982
经检验，x_{\max} = 1972。
::::
后记
原创不易，点个赞再走吧~~
求管理员通过qwq
更多精彩，关注我们的合集