位值原理与位进制进阶

· · 算法·理论

前言

这是我和盟友两位五年级蒟蒻合作的数论合集第二篇文章，大佬们不喜勿喷，感谢您的收看。

多位数表示

我们在数学学习生活中，经常碰到需要把一个数表示出来，如果位数已知，例如八位数：

\overline{abcdefgh}

但如果位数未知，最简单粗暴的方法就是表示成这样：

\overline{a_na_{n-1}a_{n-2}\dots a_1a_0}

但是 但凡上过小学的都知道 在十进制下，第 i 位的位值为 10^{i-1}，所以，一个 n+1 位数在十进制下还可以表示成这样：

\sum_{i=0}^{n}10^ia_i

推广到 k 进制，我们就可以表示为

\sum_{i=0}^{n}k^ia_i

这件事情尤为重要，将会应用在我接下来要讲述的知识点里。

多位数拆分与构造

前置芝士

我们知道

\underset{k个9}{\underbrace{99\dots9}}

可以表示为

10^k-1

那么

\forall 1 \le i \le 9,\overline{\underset{k个i}{\underbrace{ii\dots i}}}

可以表示为

\frac{i}{9} \cdot (10^k-1)

那么接下来这道题对你来说应该不是问题。

例题一

::::info[题目]{open} 求证：

\underset{k个4}{\underbrace{44\dots4}}\underset{k-1个8}{\underbrace{88\dots8}}9

一定是一个完全平方数。 ::::

根据上面的芝士，可以将上面的数按三个部分进行拆分配方。

::::success[完整证明]{open} 证：

\begin{align*} &\space\underset{k个4}{\underbrace{44\dots4}}\underset{k-1个8}{\underbrace{88\dots8}}9\\ &=10^k \cdot \frac{4}{9}(10^k-1)+10 \cdot \frac{8}{9}(10^{k-1}-1)+9\\ &=\frac{1}{9}[(10^k\times4)(10^k-1)+2 \times40(10^{k-1}-1)+9]\\ &=\frac{1}{9}(4\cdot10^{2k}+4\cdot10^k+1)\\ &=\frac{1}{9}(2\times10^k+1)^2\\ &=[\frac{1}{3}(2\times10^k+1)]^2 \end{align*}

又

3 \mid 2 \times 10^k+1

故

\frac{1}{3}(2\times10^k+1)\in\mathbb{Z}

所以

\underset{k个4}{\underbrace{44\dots4}}\underset{k-1个8}{\underbrace{88\dots8}}9=[\frac{1}{3}(2\times10^k+1)]^2

是完全平方数，证毕。 ::::

接下来这道题也同理。

例题二

::::info[题目]{open} 求证：

19\mid 120\underset{n个3}{\underbrace{33\dots3}}08

::::

类似地，可以把这个数拆开，证每一个部件都是 19 的倍数即可。

::::success[完整证明]{open} 证：

\begin{align*} &\because120\underset{n个3}{\underbrace{33\dots3}}08\\ &=120\times10^{n+2}+\frac{1}{3}(10^n-1)\times10^2+8\\ &=\frac{1}{3}[36\times10^{n+2}+10^2(10^n-1)+24]\\ &=\frac{1}{3}(361\times10^{n+2}-76)\\ &=\frac{1}{3}(19^2\times10^{n+2}-19\times4)\\ &=\frac{19}{3}(19\times10^{n+2}-4) \end{align*}

且

3 \mid 19\times10^{n+2}-4

故

19 \mid 120\underset{n个3}{\underbrace{33\dots3}}08

证毕。 ::::

下面我们来看看多位数的构造问题。

例题三

::::info[题目]{open} 构造一个平方数恰好以 2021 个 9 开头。 ::::

会做这题你先要会幼儿园就会的找规律。

这题还是不难的，首先我们知道

\begin{cases} 9^2=81\\ 99^2=9801\\ 999^2=998001\\ \dots\\ \underset{k个9}{\underbrace{99\dots9}}^2=\underset{k-1个9}{\underbrace{99\dots9}}8\underset{k-1个0}{\underbrace{00\dots0}}1 \end{cases}

那么这题构造

\underset{2022个9}{\underbrace{99\dots9}}^2=\underset{2021个9}{\underbrace{99\dots9}}8\underset{2021个0}{\underbrace{00\dots0}}1

就可以了。

::::success[完整解答]{open} 解：构造：

\begin{align*} &\underset{2022个9}{\underbrace{99\dots9}}^2\\ &=\underset{2022个9}{\underbrace{99\dots9}} \times \underset{2022个9}{\underbrace{99\dots9}}\\ &=\underset{2022个9}{\underbrace{99\dots9}} \times (10^{2022}-1) \\ &=\underset{2022个9}{\underbrace{99\dots9}} \times 10^{2022}-\underset{2022个9}{\underbrace{99\dots9}}\\ &=\underset{2021个9}{\underbrace{99\dots9}}8\underset{2021个0}{\underbrace{00\dots0}}1 \end{align*}

::::

下面看一个不一样的题目。

例题四

::::info[题目]{open} 构造一个平方数的数字和为 2020。 ::::

首先我们知道，一个数的数字和除以 9 的余数和本身除以 9 的余数相同，注意到数字和为 2020，我们令原数为 x，则

x \equiv 4 \pmod{9} \Rightarrow x \equiv \pm2 \pmod{9}

即

x \equiv 2 \text{ 或 } 7 \pmod{9}

根据这个构造列方程即可（不是 dp 动态转移方程）。

::::success[完整解答]{open} 解：

\begin{align*} \because (10^n-3)^2&=10^{2n}-6\times10^n+9\\ &=\underset{n-1个9}{\underbrace{99\dots9}}4\underset{n-1个0}{\underbrace{00\dots0}}9 \end{align*}

故只需

9n+4=2020

解得

n=224。

::::

数位分析

前置芝士

::::info[美味的芝士]{open}

:::: 这个不难理解，读者有兴趣的话可以自己列个竖式模拟一下，最前面一位进位的话就是 $m+n$，不进位就是 $m+n-1$，这件事对解决下面的题解有很大的帮助。 ~~芝士真好吃。~~ ### 例题一 ::::info[题目]{open} 求将 $2^{2022}$ 与 $5^{2022}$ 用十进制表示的总位数。 :::: 可以相乘分析。 ::::success[完整解答]{open} 解：设 $2^{2022}$ 有 $m$ 位数，$5^{2022}$ 有 $n$ 位数，则 $$ \begin{cases} 10^{m-1}<2^{2022}<10^m\\ 10^{n-1}<5^{2022}<10^n\\ \end{cases} $$ $$ \therefore 10^{x+y-2}<10^{2022}<10^{x+y} $$ 故 $$ x+y-1=2022 $$ $$ \Rightarrow x+y=2023 $$ 即共有 $2023$ 位。 :::: ### 例题二 ::::info[题目]{open} 一个 $n$ 位数的立方是 $m$ 位数，求证：$n+m \ne 2001$。 :::: 可以把这个数设为 $x$，观察 $m+n$ 对 $4$ 的余数。 ::::success[完整证明]{open} 证：设这个 $n$ 位数为 $x$，则 $$ 10^{n-1} \le x<10^n $$ $$ \therefore 10^{3n-3} \le x^3<10^{3n} $$ 于是 $$ m=3n-2,3n-1,3n $$ $$ \Rightarrow m+n=4n-2,4n-2,4n $$ $$ \therefore m+n \ne 2001。 $$ 证毕。 :::: ### 例题三 ::::info[题目]{open} 已知 $9^{4000}$ 是一个 $3817$ 位数，且首位数字为 $9$，求 $\forall 1 \le n \le 4000,9^n$ 中有多少个数字的首位数字为 $9$。 :::: 可以从进位的角度考虑，由于 $9$ 这个数字的特殊性，只有上一个 $9^n$ 的首位为 $1$，且乘 $9$ 不进位下一个 $9^{n+1}$ 的首位才能是 $9$。 ::::success[完整解答]{open} 解： $\because$ 从 $9$ 到 $9^{4000}$ 中位数增加了 $3817-1=3816$ 位。 $\therefore 9^2$ 至 $9^{4000}$ 有 $3816$ 个的首位不是 $9$。 $\therefore$ 共有 $4000-3816=184$ 个首位为 $9$。 证毕。 :::: ### 习题 留几道关于首位数字的习题。 ::::info[基础题]{open} 存在一些正整数 $n$，使得 $2^n$ 和 $5^n$ 在十进制表示下的首位数字相同，求所有这样的首位数字。 :::: ::::info[小挑战]{open} 求证：$17^n,17^{n+1},17^{n+2},17^{n+3},17^{n+4}$ 中至少有一个在十进制中首位数码为 $1$。 :::: ## 位值原理方程 ### 前置芝士 我们在做题时，经常需要把一个多位数表示出来，最直接的方法就是设成 $$ \sum_{i=0}^{m}10^ia_i $$ 但是如果几个数为在整个等量关系中相对位置没有发生任何变化，就应该将它们看作一个整体，例如 $$ 5 \times \overline{abcdef} = 8 \times \overline{defabc} $$ 就应该设 $$ \overline{abc}=x,\overline{def}=y $$ 整个问题中未知数的个数就可以减少至 $2$ 个。 ### 例题一 ::::info[题目]{open} 求一个最小的自然数，使得将它的末尾数字移至首位时，所得的数是原数的五倍。 :::: 可以考虑把各位数字表示出来，列方程，运用整除 ~~分块~~ 求解。 ::::success[完整解答]{open} 解：设这个数为 $10x+y$，其中 $y$ 为个位，$x$ 有 $k$ 位。 则 $$ 10^ky+x=5(10x+y) $$ 整理得 $$ 49x=(10^k-5)y $$ $$ \because y<10 $$ $$ \therefore 49 \nmid y $$ $$ \therefore 7 \mid 10^k-5 $$ 于是 $$ k_{min}=5 $$ 代入得 $$ 49x=99995y $$ $$ \therefore 7x=14285y $$ 故 $$ 7 \mid y \Rightarrow y=7 $$ $$ \therefore x=14285 $$ 故原数为 $142857$。 :::: ### 例题二 ::::info[题目]{open} 设 $n$ 是一个**五位数**，$m$ 为 $n$ 删去它正中间的一位数码后得到的四位数，若 $m \mid n$，求这样 $n$ 的个数。 :::: 由于 $n$ 是五位数，可以把每一位分别设出来类似地，可以使用整除 ~~分块~~ 解答。 ::::success[完整解答]{open} 解：设 $$ n=\overline{abcde},m=\overline{abde} $$ $$ \because m \mid n $$ $$ \therefore 100 \overline{ab}+\overline{de} \mid 1000 \overline{ab}+100c+ \overline{de} $$ $$ \therefore 100\overline{ab}+\overline{de} \mid 100c-\overline{de} $$ 而 $$ {-}\overline{abde}<-900<100c-9\overline{de}\le900<\overline{abde} $$ $$ \therefore 100c=9\overline{de} $$ 故 $$ \begin{cases} c=0\\ \overline{de}=0 \end{cases} $$ $$ \therefore 100\overline{ab} \mid 1000 \overline{ab} $$ 恒成立，故所有两位数 $\overline{ab}$ 均满足条件，共 $$ 99-10+1=90 $$ 个。 :::: ### 例题三 ::::info[题目]{open} 求所有的正整数满足：它的数码和加上它的数码积正好等于它本身。 :::: 这个题就需要把整个数设出来了，再进行数学归纳法。 ::::success[完整解答]{open} 解：设这个正整数为 $$ \sum_{i=0}^n10^ia_i(n \in \mathbb{N}) $$ 共 $n+1$ 位。 则 $$ \sum_{i=0}^{n}10^ia_i=\sum_{i=0}^{n}a_i+\prod_{i=0}^{n}a_i $$ $$ \therefore 10^na_n<\sum_{i=0}^{n}10^ia_i=\sum_{i=0}^{n}a_i+\prod_{i=0}^{n}a_i\le 9n+a_n+9^na_n $$ 下证：当 $n \ge 2$ 时， $$ 10^n \ge 9^n+9n+1 $$ 证： $1^\circ$ 当 $n=2$ 时， $$ 10^2=9^2+9\times2+1 $$ 命题成立。 $2^\circ$ 若 $n=k$ 时命题成立，即 $$ 10^k\ge9^k+9k+1 $$ 则 $n=k+1$ 时， $$ 10^{k+1}\ge10\cdot9^k+90k+10\ge9^{k+1}+9k+10 $$ 命题也成立。 $\therefore$ 由数学归纳法，原命题成立，即 $$ \therefore n=1 \Rightarrow 10a_1+a_0=a_1a_0+a_1+a_0 $$ $$ \therefore 9a_1=a_1a_0 $$ $$ \therefore \begin{cases} a_0=9\\ 1 \le a_1 \le 9 \end{cases} $$ 故满足条件的多位数有 $$ 19, 29, 39, 49, 59, 69, 79, 89, 99。 $$ :::: ### 例题四 ::::info[题目]{open} 试找 $4$ 个百位相同的三位数，使得其中有 $3$ 个整除它们的和。 :::: 可以把 $4$ 个三位数被 $S$ 除的商为 $a_1,a_2,a_3,a_4$，和为 $S$，再使用[多元有序对称枚举](https://www.luogu.com.cn/article/ijfqsqnr)即可。 ::::success[完整解答]{open} 解：设和为 $S$，$4$ 个三位数为 $$ \frac{S}{a_i},1 \le i \le 4 $$ 且 $a_1<a_2<a_3$ 均为整数，百位均为 $b$，则 $$ \therefore \sum_{i=1}^4\frac{S}{a_i}=S $$ $$ \because S \ne 0 $$ $$ \therefore \sum_{i=1}^4\frac{1}{a_i}=1 $$ 引： $$ \forall 1\le i,j\le4,\frac{a_i}{a_j}=\frac{\frac{S}{a_i}}{\frac{S}{a_j}}<\frac{100(b+1)}{b}=\frac{b+1}{b}<2 $$ 枚举： $1^\circ \space a_1=2$ 则 $a_2 \ge 3,a_3\ge4=2a_1$ 矛盾。 $2^\circ \space a_1=3$ 则 $3<a_2<a_3<6$，故 $a_2=4,a_3=5$， $$ a_4=(1-\frac1 3-\frac1 4-\frac1 5)^{-1}=\frac{60}{13} $$ 又 $$ \frac{S}{3},\frac{S}{4},\frac{S}{5},\frac{13S}{60}\in\mathbb{Z} $$ $$ \therefore 60 \mid S $$ 又由于百位相同，于是 $$ \frac{S}{3}-\frac{S}{5}<100 $$ $$ \therefore S<750 $$ 又 $$ S\ge400b $$ 故 $$ b=1,\frac{S}{3}<200,\frac{S}{5}>100 $$ $$ \therefore 500<S<600 $$ $$ \therefore S=540 $$ --- $3^\circ\space a_1\ge4,a_2\ge5,a_3\ge6$，此时 $$ a_4\le(1-\frac14-\frac15-\frac16)^{-1}=\frac{60}{23} $$ $$ \therefore a_3>2a_4 $$ 矛盾。 综上，满足条件的三位数为 $180, 135, 108, 117$。 :::: ### 习题 ::::info[基础题]{open} 试求所有的正整数 $A$，满足： 在 $A$ 的右端多写三位数，使得所得到的数等于由 $1$ 到 $A$ 的所有正整数之和。 :::: ::::info[小挑战]{open} 一个多位数的数字和是它数字和的 $111$ 倍，求这个多位数。 ::::info[提示]{open} 表示出来后先数学归纳法证明 $$ 10^n>999(n+1) $$ 然后同余方程解决。 :::: ## 其他进制 话不多说，咱直接上题目，因为进制这种东西 OIer 应该都知道。 ### 例题一 ::::info[题目]{open} 求证； $$ \forall n \ge 2, n \in \mathbb{N},\exists k \in \mathbb{Z},(10201)_n=k^2 $$ :::: 直接转换成十进制即可。 ::::success[完整证明]{open} 证： $$ \begin{aligned} (10201)_n&=n^4+2n^2+1\\ &=(n^2+1)^2 \end{aligned} $$ 证毕。 :::: 简单的题就不多说了，最后再来看一道稍有难度的题目。 ### 例题二 ::::info[题目]{open} 定义 $r(n)$ 是对于正整数 $n$ 的一个函数，满足 $$ \begin{cases} r(1)=1\\ r(2m)=r(m)\\ r(2m+1)=r(m)+1 \end{cases} $$ 已知 $1 \le k \le 10000$，求 $r(k)$ 的最大值。 :::: 通过手搓 ~~样例~~ 递推式可以发现，$r(k)$ 其实就是二进制下 $k$ 的数字和，**第二**数学归纳法证明即可。 ::::success[完整解答]{open} 解：下证：设 $s(n)$ 为二进制下 $n$ 的数字和，则 $r(n)=s(n)$。 证：$1^\circ$ 当 $n=1$ 时，$r(1)=s(1)=1$，命题成立。 $2^\circ$ 若 $n\le k$ 时，命题成立，即 $\forall 1 \le n \le k,r(n)=s(n)$，则 $n=k+1$ 时，考虑分类讨论： $(1) k+1 \equiv 0 \pmod{2}$，则 $$ r(k+1)=r\left(\frac{k+1}{2}\right) $$ 由归纳假设， $$ r\left(\frac{k+1}{2}\right)=s\left(\frac{k+1}{2}\right) $$ 又 $$ s(k+1)=s\left(\frac{k+1}{2}\right) $$ $$ \therefore r(k+1)=s(k+1) $$ --- $(2)k+1 \equiv 1 \pmod{2}$，则 $$ r(k+1)=r\left(2\cdot\frac{k}{2}+1\right)=r\left(\frac{k}{2}\right)+1 $$ 由归纳假设， $$ r\left(\frac{k}{2}\right)=s\left(\frac{k}{2}\right) $$ 又 $$ s\left(\frac{k}{2}\right)=s(k) $$ $$ \therefore r(k+1)=s(k+1) $$ --- 综上，由数学归纳法，原命题成立，即 $$ \forall n \in \mathbb{Z},r(n)=s(n) $$ $$ \because 2^{14}-1>10000 $$ $$ \therefore r(k)<14 $$ 又由于当 $k=2^{13}-1=8191$ 时，$r(k)=13$，故 $r(k)$ 的最大值为 $13$。 :::: ### 习题 ::::info[基础题]{open} 已知整数 $n$，满足：它的 $b$ 进制表示为 $777$，求整数 $b$ 的最小值，使得 $n$ 是十进制整数的 $4$ 次方。 :::: ::::info[小挑战]{open} 在 $6$ 进制中有三位数 $\overline{abc}$，化为 $9$ 进制为 $\overline{cba}$，求这个三位数在十进制表示下为多少？ ::::info[提示] 骗你的，这次没有友情提示。 :::: ## 后记 **原创不易，点个赞再走吧~~** **求管理员通过 qwq。** [更多精彩，关注我们的合集](https://www.luogu.com.cn/article/4y3zfcw5)。