跳到正文
数论 · 第 27 章

进制

每种进制都是一条“满几进一”的规则:把一个数按进制的幂展开,就能解出各位数字,或者取模直接读出余数。

你需要先会
在 YouTube 上打开
27.00%

任意进制中的位值

在本节中,你将能够 把任意进制的数读成关于进制的多项式,在两个方向上做进制转换,并且不用转换就求出余数。

27,006,000,052927{,}006{,}000{,}052_{9} 能被 55 整除吗?你不需要把十一位数字全部换算。只需要知道 99 模 55 是多少。

进制是一条“满几进一”的规则。十进制满十进一;bb 进制满 bb 进一。所以每一位的位值是 bb 的一个幂,一个数就是关于 bb 的多项式:(a2a1a0)b=a2b2+a1b+a0(a_2 a_1 a_0)_b = a_2 b^2 + a_1 b + a_0。

大多数竞赛题靠两招就能解决。展开:把数写成多项式,解出各位数字。数字是 00 到 b−1b - 1 之间的整数,这是很强的条件。或者把进制对 mm 取模,不用转换就求出余数。

注意:

b≡1(modb−1)b \equiv 1 \pmod{b - 1},所以一个 bb 进制数模 b−1b - 1 的余数和它的数字和相同。这就是“能被 9 整除”的判定法则,在任何进制下都成立。

动手探索先玩,再学公式

5 进制的 44 = 十进制的 24

进制 b5
模 m关
0525^{2}
4515^{1}
4505^{0}
445 = 24

5 进制的 44 = 24

认识概念

定义 27.0.1 · 进制

用 nn 进制表示一个数,和 1010 进制类似,只是不再每满 1010 进到下一个位值,而是每满 nn 就进一位。

概念 27.0.2 · $n$ 进制中的位值

各位数字为 am,am−1,…,a2,a1,a0a_m, a_{m-1}, \ldots, a_2, a_1, a_0 的 nn 进制数可以写成

(amam−1…a2a1a0)n.\left(a_m a_{m-1} \ldots a_2 a_1 a_0\right)_n.

它的值是

amnm+am−1nm−1+⋯+a2n2+a1n1+a0n0.a_m n^m + a_{m-1} n^{m-1} + \cdots + a_2 n^2 + a_1 n^1 + a_0 n^0.

概念 27.0.3 · $n$ 进制小数

进制里也可以有小数,包括循环小数和有限小数。

小数点前各位数字为 am,am−1,…,a1,a0a_m, a_{m-1}, \ldots, a_1, a_0、小数点后各位数字为 a−1,a−2,…,a−qa_{-1}, a_{-2}, \ldots, a_{-q} 的 nn 进制数可以写成

(amam−1…a1a0 . a−1a−2…a−q)n.\left(a_m a_{m-1} \ldots a_1 a_0 \,.\, a_{-1} a_{-2} \ldots a_{-q}\right)_n.

它的值是

amnm+am−1nm−1+⋯+a1n1+a0n0+a−1n−1+a−2n−2+⋯+a−qn−q.a_m n^m + a_{m-1} n^{m-1} + \cdots + a_1 n^1 + a_0 n^0 + a_{-1} n^{-1} + a_{-2} n^{-2} + \cdots + a_{-q} n^{-q}.

看例题先预测,再揭晓

例 27.1

AMC 10/12

数 NN 的九进制表示是 27,006,000,052九27{,}006{,}000{,}052_{\text{九}}。NN 除以 55 的余数是多少?

进制里程表 (总数在例题最后一步揭晓)

进制 b9
模 m关
29109^{10}
7999^{9}
0989^{8}
0979^{7}
6969^{6}
0959^{5}
0949^{4}
0939^{3}
0929^{2}
5919^{1}
2909^{0}
270060000529 = ? (例题最后一步揭晓)

9 进制的 27006000052 = ?

  1. 1

    把十一位数字全部换算太慢了。换个思路:99 除以 55 的余数是多少?

    先预测一下:
在 YouTube 上打开

例 27.2

AIME

求三位正整数 a‾ b‾ c‾\underline{a}\,\underline{b}\,\underline{c},它的九进制表示是 b‾ c‾ a‾ 九\underline{b}\,\underline{c}\,\underline{a}_{\,\text{九}},其中 aa、bb、cc 是(不一定互不相同的)数字。

进制里程表 (总数在例题最后一步揭晓)

进制 b9
模 m关
1929^{2}
0919^{1}
0909^{0}
1009 = 81

同样的数字按 10 进制读: 100

9 进制的 100 = 81

  1. 1

    按位值把两个数都展开。b‾ c‾ a‾ 九\underline{b}\,\underline{c}\,\underline{a}_{\,\text{九}} 等于多少?

    先预测一下:
    点击一个选项,或输入它的字母(A–E)。
在 YouTube 上打开

例 27.3

AMC 10

随机选取一个十进制三位数 nn。nn 的 9 进制表示和 11 进制表示都是三位数的概率最接近下列哪个值?

  1. (A)0.30.3
  2. (B)0.40.4
  3. (C)0.50.5
  4. (D)0.60.6
  5. (E)0.70.7

进制里程表 (总数在例题最后一步揭晓)

第一个进制9
第二个进制11
位数3
  • 范围:100–999
  • 9 进制:81–728 是 3 位数
  • 11 进制:121–1,330 是 3 位数
  • 范围内两者都满足:?–?
? (例题最后一步揭晓)

9 进制和 11 进制都满足:? 个数

  1. 1

    哪些数在 99 进制下恰好是三位数?写出最大的那个。

    先预测一下:
在 YouTube 上打开

例 27.4

AMC 12

对某个正整数 kk,(十进制)分数 751\frac{7}{51} 的 kk 进制循环小数表示是 0.23‾k=0.232323…k0.\overline{23}_k = 0.232323\ldots_k。kk 等于多少?

进制里程表 (总数在例题最后一步揭晓)

进制 b10
210−110^{-1}
310−210^{-2}
0.23‾10=23102−1=23990.\overline{23}_{10} = \tfrac{23}{10^{2} - 1} = \tfrac{23}{99}≈ 0.23232323

目标 7/51: ? (例题最后一步揭晓)

10 进制循环小数 0.(23) = 23/99

  1. 1

    由概念 27.0.3,第一节 0.23k0.23_k 的值是多少?

在 YouTube 上打开

自己做

习题 27.1.1

AMC 10

在 1010 进制中,数 20132013 的末位数字是 33。而在 99 进制中,同一个数写作 (2676)9(2676)_{9},末位数字是 66。有多少个正整数 bb,使 20132013 的 bb 进制表示的末位数字是 33?

习题 27.1.5

AMC 10

下列哪个整数 bb 使 bb 进制数 2021b−221b2021_b - 221_b 不能被 33 整除?

8 进制的 0 = 十进制的 0;模 3 余 0

进制 b8
模 m3
0838^{3}≡2
0828^{2}≡1
0818^{1}≡2
0808^{0}≡1
08 = 0

把每个位值换成它模 3 的余数:

0 = 0

模 3 的余数: 0

8 进制的 0 = 0

点击一个选项,或输入它的字母(A–E)。

习题 27.1.6

AMC 10

设 nn 是正整数,dd 是一个数字,使得 nn 进制数 32d‾\underline{32d} 的值等于 263263,并且 nn 进制数 324‾\underline{324} 的值等于六进制数 11d1‾\underline{11d1} 的值。n+dn + d 等于多少?

竞赛角真实竞赛题

习题 27.1.2

AMC 10

十六进制(16 进制)数用数字 00 到 99 以及字母 AA 到 FF 来书写,字母表示 1010 到 1515。在前 10001000 个正整数中,有 nn 个数的十六进制表示只含数字(不含字母)。nn 的各位数字之和是多少?

16 进制的 3E8 = 十进制的 1,000

进制 b16
模 m关
316216^{2}
E16116^{1}
816016^{0}
3E816 = 1,000

16 进制的 3E8 = 1,000

习题 27.1.4

AIME

正整数 NN 的十一进制表示是 a‾ b‾ c‾\underline{a}\,\underline{b}\,\underline{c},八进制表示是 1‾ b‾ c‾ a‾\underline{1}\,\underline{b}\,\underline{c}\,\underline{a},其中 aa、bb、cc 表示(不一定互不相同的)数字。求满足条件的最小的 NN,用十进制表示。

习题 27.1.11(补充题)

AIME

数 nn 在 1414 进制下可以写成 a‾ b‾ c‾\underline{a}\,\underline{b}\,\underline{c},在 1515 进制下可以写成 a‾ c‾ b‾\underline{a}\,\underline{c}\,\underline{b},在 66 进制下可以写成 a‾ c‾ a‾ c‾\underline{a}\,\underline{c}\,\underline{a}\,\underline{c},其中 a>0a > 0。求 nn 的十进制表示。

习题 27.1.12(补充题)

AIME

如果正整数 NN 的 77 进制表示的各位数字组成的 1010 进制数恰好是 NN 的两倍,就称 NN 为 7-10 双倍数\textit{7-10 双倍数}。例如,5151 是一个 7-10 双倍数,因为它的 77 进制表示是 102102。最大的 7-10 双倍数是多少?

7 进制的 102 = 十进制的 51;同样的数字按 10 进制读是 102

进制 b7
模 m关
1727^{2}
0717^{1}
2707^{0}
1027 = 51

同样的数字按 10 进制读: 102= 2 × 原值

7 进制的 102 = 51

习题 27.1.13(补充题)

AIME

设 NN 是满足以下条件的正整数的个数:不超过 20032003,并且 22 进制表示中 11 的个数多于 00 的个数。求 NN 除以 10001000 的余数。

2 进制的 11111010011 = 十进制的 2,003

进制 b2
模 m关
12102^{10}
1292^{9}
1282^{8}
1272^{7}
1262^{6}
0252^{5}
1242^{4}
0232^{3}
0222^{2}
1212^{1}
1202^{0}
111110100112 = 2,003

2 进制的 11111010011 = 2,003

习题 27.1.15(补充题)

AIME

求不超过 20172017、且三进制表示中不含数字 00 的正整数的个数。

过关检测(第 27.0 节)

3 题中答对 2 题即可掌握本节。每题只有一次机会,没有提示。
1

123451234_5 在 1010 进制中是多少?

2

121212131212121_3 除以 44 的余数是多少?

3

把 55 进制循环小数 0.3‾5=0.333…50.\overline{3}_5 = 0.333\ldots_5 写成 1010 进制的分数。

27.1

练习题

在本节中,你将能够 在更难的进制问题中综合运用位值、数字的限制和取模。

该把几招混起来用了。每道题都藏着某种进制下的多项式:展开它,利用数字的限制,或者取模。卡住了的话,每道题都有三条提示。

想在一页上看到本章的所有题目?打开习题集。

综合练习

习题 27.1.7(补充题)

AMC 10

这道题在书中还以 27.1.6 的编号出现。

设 nn 是正整数,dd 是一个数字,使得 nn 进制数 32d‾\underline{32d} 的值等于 263263,并且 nn 进制数 324‾\underline{324} 的值等于六进制数 11d1‾\underline{11d1} 的值。n+dn + d 等于多少?

习题 27.1.8(补充题)

AMC 10

这道题在书中还以 27.1.5 的编号出现。

下列哪个整数 bb 使 bb 进制数 2021b−221b2021_b - 221_b 不能被 33 整除?

点击一个选项,或输入它的字母(A–E)。

习题 27.1.9(补充题)

AMC 10

小于 20192019 的正整数的七进制表示中,各位数字之和最大可能是多少?

习题 27.1.10(补充题)

AMC 12

在下面的等式中,AA 和 BB 是连续的正整数,AA、BB 和 A+BA + B 都表示进制:

132A+43B=69A+B.132_A + 43_B = 69_{A+B}.

A+BA + B 等于多少?

竞赛角真实竞赛题

习题 27.1.3

AIME

对每个正整数 nn,设 f(n)f(n) 为 nn 的四进制表示的各位数字之和,g(n)g(n) 为 f(n)f(n) 的八进制表示的各位数字之和。例如 f(2020)=f(1332104)=10=128f(2020) = f(133210_{\text{4}}) = 10 = 12_{\text{8}},而 g(2020)=128 的数字和=3g(2020) = 12_{\text{8}} \text{ 的数字和} = 3。设 NN 是使 g(n)g(n) 的十六进制表示不能只用数字 00 到 99 写出的最小的 nn。求 NN 除以 10001000 的余数。

习题 27.1.14(补充题)

AIME

一个有理数用八进制写作 a‾ b‾ . c‾ d‾\underline{a}\,\underline{b}\,.\,\underline{c}\,\underline{d},其中所有数字都不为零。同一个数用十二进制写作 b‾ b‾ . b‾ a‾\underline{b}\,\underline{b}\,.\,\underline{b}\,\underline{a}。求十进制数 a‾ b‾ c‾\underline{a}\,\underline{b}\,\underline{c}。

8 进制的 0.00 = 0

进制 b8
0818^{1}
0808^{0}
.
08−18^{-1}
08−28^{-2}
0.008 = 0

8 进制的 0.00 = 0

习题 27.1.16(补充题)

AIME

这道题在书中还以 27.1.11 的编号出现。

数 nn 在 1414 进制下可以写成 a‾ b‾ c‾\underline{a}\,\underline{b}\,\underline{c},在 1515 进制下可以写成 a‾ c‾ b‾\underline{a}\,\underline{c}\,\underline{b},在 66 进制下可以写成 a‾ c‾ a‾ c‾\underline{a}\,\underline{c}\,\underline{a}\,\underline{c},其中 a>0a > 0。求 nn 的十进制表示。

习题 27.1.17(补充题)

AIME

求所有满足以下条件的正整数 b<1000b < 1000 之和:bb 进制整数 36b36_b 是完全平方数,且 bb 进制整数 27b27_b 是完全立方数。

习题 27.1.18(补充题)

AIME

这道题在书中还以 27.1.4 的编号出现。

正整数 NN 的十一进制表示是 a‾ b‾ c‾\underline{a}\,\underline{b}\,\underline{c},八进制表示是 1‾ b‾ c‾ a‾\underline{1}\,\underline{b}\,\underline{c}\,\underline{a},其中 aa、bb、cc 表示(不一定互不相同的)数字。求满足条件的最小的 NN,用十进制表示。

习题 27.1.19(补充题)

AIME

存在唯一的 rr 个非负整数 n1>n2>⋯>nrn_1 > n_2 > \cdots > n_r 和唯一的 rr 个整数 aka_k(1≤k≤r1 \le k \le r),每个 aka_k 为 11 或 −1-1,使得

a13n1+a23n2+⋯+ar3nr=2008.a_1 3^{n_1} + a_2 3^{n_2} + \cdots + a_r 3^{n_r} = 2008.

求 n1+n2+⋯+nrn_1 + n_2 + \cdots + n_r。

0 的平衡三进制 = 0

0373^{7}
0363^{6}
0353^{5}
0343^{4}
0333^{3}
0323^{2}
0313^{1}
0303^{0}

数字只用 −1、0、1。每个整数恰好有一种这样的写法。

00 = 0

目标 2,008: 还差 +2,008

0 的平衡三进制:0

习题 27.1.20(补充题)

AIME

这道题在书中还以 27.1.3 的编号出现。

对每个正整数 nn,设 f(n)f(n) 为 nn 的四进制表示的各位数字之和,g(n)g(n) 为 f(n)f(n) 的八进制表示的各位数字之和。例如 f(2020)=f(1332104)=10=128f(2020) = f(133210_{\text{4}}) = 10 = 12_{\text{8}},而 g(2020)=128 的数字和=3g(2020) = 12_{\text{8}} \text{ 的数字和} = 3。设 NN 是使 g(n)g(n) 的十六进制表示不能只用数字 00 到 99 写出的最小的 nn。求 NN 除以 10001000 的余数。

习题 27.1.21(补充题)

AMC 10挑战

Bernardo 选了一个三位正整数 NN,并把它的 55 进制和 66 进制表示都写在黑板上。后来 LeRoy 看到了 Bernardo 写的这两个数。他把这两个数当作 1010 进制整数相加,得到整数 SS。例如,若 N=749N = 749,Bernardo 写下 10,44410{,}444 和 3,2453{,}245,LeRoy 得到和 S=13,689S = 13{,}689。有多少种 NN 的选法,使 SS 的最右边两位数字(按顺序)与 2N2N 的最右边两位数字相同?