题目导航

林老师 · 客观题题库 · 专题 10 数论基础 · 复习强化

专题 10 数论基础 · 复习强化

100 题 · 每题对应一个知识细节 · 全部原创

真题
复刻

试卷编号ORIG-专题10数论基础-复习强化

题目总数106 题 · 100 分

试卷类型客观题

考生须知：
① 本卷共 9 大部分，合计 106 题 · 100 分，全部为客观题；
② 试卷右上角设有 「提交答卷」 与 「重置考试」 按钮，提交后系统自动判分并显示答题正确情况，请确认全部作答后再行提交；
③ 试卷不显示答案，提交后方可查看每题作答与正确答案的对照；
④ 答卷进度会保留在本地缓存中，刷新或再次打开仍可继续作答；
⑤ 本卷仅供学生练习使用；请勿用于其他用途；题面有问题请联系：i64coder@163.com。

判分报告

0 / 100 分

答对 · 得 0 分

答错 · 失 0 分

未作答

当前筛选下没有题目

壹

整除与模运算

14 QUESTIONS · 2 POINTS EACH

第 1 题 A1 未作答

$a \mid b$ （ $a$ 整除 $b$ ）的含义是（）。

（1 分）

$a$ 等于 $b$

$a$ 小于 $b$

存在整数 $k$ 使 $b = ka$ ——即 $b$ 除以 $a$ 的余数为 $0$

$a$ 大于 $b$

第 2 题 A2 未作答

$a \bmod b$ 的结果是（）。

（1 分）

$a$ 减去 $b$

$a$ 乘以 $b$

$a$ 除以 $b$ 的余数

$a$ 除以 $b$ 的商

第 3 题 A3 未作答

$a \bmod b$ （ $a \ge 0, b > 0$ ）的结果范围是（）。

（1 分）

$1$ 到 $b$

$0$ 到 $b-1$

$0$ 到 $b$

$1$ 到 $b-1$

第 4 题 A4 未作答

$17 = 5 \times 3 + 2$ 中，商和余数分别是（）。

（1 分）

$3$ 和 $2$

$3$ 和 $5$

$5$ 和 $2$

$5$ 和 $3$

第 5 题 A5 未作答

$(a + b) \bmod m$ 等价于（）。

（1 分）

$(a \bmod m) + (b \bmod m)$ （不需要再取模）

$(a \bmod m) \times (b \bmod m)$

$((a \bmod m) + (b \bmod m)) \bmod m$

$(a + b) \bmod (2m)$

第 6 题 A6 未作答

C++ 中 $-7 \% 3$ 的结果是（）。

（1 分）

$-2$

$-1$

$1$

$2$

第 7 题 A7 未作答

如果 $a \bmod m == 0$ 且 $b \bmod m == 0$ ，则 $(a + b) \bmod m$ 一定是（）。

（1 分）

$1$

$0$

不确定

$m$

第 8 题 A8 未作答

$\lfloor 7/2 \rfloor$ 的值是（）。

（1 分）

$7$

$3.5$

$4$

$3$

第 9 题 A9 未作答

$\lceil 7/2 \rceil$ 的值是（）。

（1 分）

$3$

$3.5$

$4$

$8$

第 10 题 A10 未作答

C++ 中 7 / 2（两个 int 相除）的结果等价于（）。

（1 分）

$\lfloor 7/2 \rfloor = 3$

$\lceil 7/2 \rceil = 4$

$7$

$3.5$

第 11 题 A11 未作答

$(x \bmod m) \bmod m$ 等于（）。

（1 分）

$m$

$x \bmod m$ ——第一次取模已在 $[0, m-1]$ 内，再取模不变

$0$

$x$

第 12 题 A12 未作答

计算 $2^{100} \bmod 7$ 时不能直接算 $2^{100}$ （溢出），正确做法是（）。

（1 分）

用浮点数

无法计算

每一步乘法后都立即 $\bmod 7$ ，让中间结果始终在 $[0, 6]$ 范围内

先算 $2^{100}$ 再取模

第 13 题 A13 未作答

$n$ 个人围圈，当前第 $i$ 人的下一位是 $(i+1) \bmod n$ 。当 $i = n-1$ 时，下一位是（）。

（1 分）

$n$

$0$

$1$

$n-1$

第 14 题 A14 未作答

$100 \bmod 7 = ?$ 、 $100 \bmod 3 = ?$ 分别是（）。

（1 分）

$2$ 和 $1$

$3$ 和 $2$

$2$ 和 $0$

$14$ 和 $33$

贰

素数与合数

14 QUESTIONS · 2 POINTS EACH

第 15 题 B1 未作答

素数（质数）的定义是（）。

（1 分）

大于 $1$ 且只能被 $1$ 和自身整除的正整数

不能被 $2$ 整除的数

所有奇数

只能被 $1$ 整除的数

第 16 题 B2 未作答

合数的定义是（）。

（1 分）

大于 $100$ 的数

负数

偶数

大于 $1$ 且除了 $1$ 和自身外还有其他因数的正整数

第 17 题 B3 未作答

$1$ 是（）。

（1 分）

既是素数也是合数

既不是素数也不是合数——素数要求"大于 $1$ "

素数

合数

第 18 题 B4 未作答

最小的素数是（）。

（1 分）

$3$

$2$

$1$

$0$

第 19 题 B5 未作答

下列数中是素数的是（）。

（1 分）

$91$

$87$

$89$

$93$

第 20 题 B6 未作答

判定 $n$ 是否为素数的试除法是（）。

（1 分）

用 $2$ 到 $n-1$ 的每个整数去试除

不需要判定，查表即可

只用 $2$ 去除

用 $2$ 到 $\sqrt{n}$ 的每个整数去试除 $n$ ——全都除不尽则为素数

第 21 题 B7 未作答

素数判定只需试除到 $\sqrt{n}$ ，原因是（）。

（1 分）

大于 $\sqrt{n}$ 的数不可能是因数

若 $n$ 有大于 $\sqrt{n}$ 的因数 $d$ ，则 $n/d < \sqrt{n}$ 也是因数——早该被发现了

$\sqrt{n}$ 之后没有整数

习惯如此

第 22 题 B8 未作答

单次素数判定（试除到 $\sqrt{n}$ ）的时间复杂度是（）。

（1 分）

$O(\log n)$

$O(n)$

$O(\sqrt{n})$

$O(1)$

第 23 题 B9 未作答

$100$ 以内最大的素数是（）。（2019 年真题）

（1 分）

$93$

$89$

$91$

$97$

第 24 题 B10 未作答

关于偶数与素数的关系，正确的是（）。

（1 分）

$2$ 是唯一的偶素数；其余偶数都是合数（能被 $2$ 整除）

偶数和素数无关

所有偶数都是素数

没有偶素数

第 25 题 B11 未作答

素数的个数是（）。

（1 分）

无穷多个（欧几里得反证法证明）

恰好 $10^6$ 个

未知

有限的

第 26 题 B12 未作答

孪生素数是指（）。

（1 分）

和为素数的两个数

两个相同的素数

差恰好为 $2$ 的一对素数（如 $11$ 和 $13$ 、 $17$ 和 $19$ ）

两个连续的合数

第 27 题 B13 未作答

随着数字增大，素数的分布（）。

（1 分）

均匀分布

越来越稀疏——但仍有无穷多个（素数定理给出近似密度 $\frac{1}{\ln n}$ ）

越来越密集

到某个数后就没了

第 28 题 B14 未作答

关于素数，错误的是（）。

（1 分）

所有奇数都是素数

素数有无穷多个

$2$ 是唯一的偶素数

试除到 $\sqrt{n}$ 即可判定

叁

素数筛法

12 QUESTIONS · 2 POINTS EACH

第 29 题 C1 未作答

素数筛法的核心思想是（）。

（1 分）

随机抽取素数

用公式直接生成

从小到大标记合数（把每个素数的倍数划掉），剩下的就是素数——"筛掉"合数

逐个判定每个数是否为素数

第 30 题 C2 未作答

埃氏筛筛 $2 \sim 20$ 的素数：从 $2$ 开始标记 $2$ 的倍数、再到 $3$ 标记 $3$ 的倍数……最终未被标记的是（）。

（1 分）

$2, 3, 5, 7, 11, 13, 17, 19$

$1, 2, 3, 5, 7$

$2, 3, 5, 7, 9, 11$

$2, 3, 4, 5, 6$

第 31 题 C3 未作答

埃氏筛代码的核心双重循环是（）。

（1 分）

外层从 $1$ 到 $n$ ，内层从 $1$ 到 $i$

只有一层循环

外层枚举 $i$ 从 $2$ 到 $n$ ，若 $i$ 未被标记则内层 $j$ 从 $i^2$ 开始步长 $i$ 标记 $j$ 为合数

递归实现

第 32 题 C4 未作答

埃氏筛的时间复杂度是（）。

（1 分）

$O(n \sqrt{n})$

$O(n)$

$O(n \log n)$

$O(n \log \log n)$ ——接近线性

第 33 题 C5 未作答

埃氏筛中 $12$ 会被标记几次（分别被哪些素数的筛循环标记）（）。

（1 分）

$2$ 次（被 $2$ 标记一次、被 $3$ 标记一次）——重复标记正是埃氏筛不如线性筛的地方

$2$ 次（被 $2$ 和 $3$ 标记）

$0$ 次

$1$ 次（只被 $2$ 标记）

第 34 题 C6 未作答

线性筛（欧拉筛）避免重复标记的关键是（）。

（1 分）

从大到小筛

使用哈希表

跳过所有偶数

每个合数只被其最小质因子筛一次——当 $i \bmod p == 0$ 时立即跳出内层循环

第 35 题 C7 未作答

线性筛代码中 if (i % primes[j] == 0) break; 的作用是（）。

（1 分）

发现 $i$ 是合数

提高精度

终止程序

保证每个合数只被其最小质因子筛掉——如果 $i$ 已能被 $primes[j]$ 整除，则更大的 $i \times primes[j+1]$ 的最小质因子仍是 $primes[j]$ ，不应在此处标记

第 36 题 C8 未作答

线性筛的时间复杂度是（）。

（1 分）

$O(n \log n)$

$O(n)$ ——每个合数恰好被标记一次

$O(n \sqrt{n})$

$O(n \log \log n)$

第 37 题 C9 未作答

线性筛相对埃氏筛的优势是（）。

（1 分）

不需要数组

代码更短

空间更小

$O(n)$ 严格线性（埃氏筛 $O(n \log \log n)$ 有重复标记），且能顺便求出每个数的最小质因子

第 38 题 C10 未作答

筛法适合的场景是（）。

（1 分）

求两个数的 gcd

需要判断大量数是否为素数（预筛 $1 \sim N$ 的素数表）

只判断一个数是否为素数

分解质因数

第 39 题 C11 未作答

用埃氏筛筛出 $1 \sim 30$ 之间的素数个数是（）。

（1 分）

$10$

$12$

$8$

$15$

第 40 题 C12 未作答

关于素数筛法，错误的是（）。

（1 分）

埃氏筛从每个素数的平方开始标记

线性筛必须用递归实现

线性筛保证每个合数只标记一次

埃氏筛的 $O(n \log \log n)$ 来自调和级数

肆

质因数分解

12 QUESTIONS · 2 POINTS EACH

第 41 题 D1 未作答

整数唯一分解定理（算术基本定理）说的是（）。

（1 分）

所有合数都是偶数

每个大于 $1$ 的正整数都可以唯一地表示为若干个素数的乘积（不计顺序）

素数有无穷多个

每个数都可以分解为两个素数之和

第 42 题 D2 未作答

$72$ 的质因数分解是（）。

（1 分）

$72 = 2^3 \times 3^2$

$72 = 8 \times 9$

$72 = 2 \times 3 \times 12$

$72 = 2 \times 36$

第 43 题 D3 未作答

用试除法分解 $60$ ：先用 $2$ 除尽得 $30$ 、再除尽得 $15$ ；换 $3$ 除尽得 $5$ ； $5$ 是素数。分解结果是（）。

（1 分）

$60 = 2^2 \times 3 \times 5$

$60 = 2 \times 30$

$60 = 2 \times 3 \times 5$

$60 = 4 \times 15$

第 44 题 D4 未作答

试除法分解 $n$ 的代码框架中，外层循环变量 $i$ 应从（）开始。

（1 分）

$n$

$2$ （最小的素数）

$0$

$1$

第 45 题 D5 未作答

试除法分解中，当 $i \times i > n$ 时可以停止，原因是（）。

（1 分）

循环变量溢出

习惯如此

程序溢出

此时的 $n$ （剩余部分）如果没有小于 $\sqrt{n}$ 的因子，则它本身是素数——直接作为最后一个质因子

第 46 题 D6 未作答

$120 = 2^3 \times 3 \times 5$ ，最大质因子是（）。

（1 分）

$120$

$3$

$2$

$5$

第 47 题 D7 未作答

$120$ 分解为 $2^3 \times 3 \times 5$ ，按从小到大输出所有质因子（含重复）是（）。

（1 分）

5 3 2 2 2

2 3 5

2 2 2 3 5

8 3 5

第 48 题 D8 未作答

$84$ 的质因数分解是（）。

（1 分）

$84 = 2 \times 42$

$84 = 4 \times 21$

$84 = 2^2 \times 3 \times 7$

$84 = 2^2 \times 21$

第 49 题 D9 未作答

已知 $n = p^a \times q^b$ （ $p, q$ 为不同素数）， $n$ 的约数个数是（）。

（1 分）

$p \times q$

$a + b$

$a \times b$

$(a+1)(b+1)$ ——每个指数从 $0$ 到 $a$ （或 $b$ ）独立取值

第 50 题 D10 未作答

$360 = 2^3 \times 3^2 \times 5^1$ ，质因子 $2$ 的指数是（）。

（1 分）

$360$

$2$

$3$

$1$

第 51 题 D11 未作答

试除法分解 $n$ 的时间复杂度是（）。

（1 分）

$O(n \log n)$

$O(\log n)$

$O(n)$

$O(\sqrt{n})$ ——试除到 $\sqrt{n}$ 即可

第 52 题 D12 未作答

关于质因数分解，错误的是（）。

（1 分）

每个大于 $1$ 的整数都有唯一的质因数分解

剩余部分大于 $1$ 时要继续分解

分解结果中可以出现合数因子

分解从小到大试除

伍

约数

12 QUESTIONS · 2 POINTS EACH

第 53 题 E1 未作答

$a$ 是 $b$ 的约数（因数），指的是（）。

（1 分）

$a$ 大于 $b$

$a$ 整除 $b$ （ $b \bmod a = 0$ ）

$a$ 等于 $b$

$a$ 和 $b$ 互素

第 54 题 E2 未作答

$12$ 的所有约数（正因数）是（）。

（1 分）

$1, 2, 3, 4, 6, 12$

$1, 2, 3$

$2, 3, 4, 6$

只有 $12$

第 55 题 E3 未作答

若 $n = p_1^{a_1} \times p_2^{a_2} \times \cdots$ ，则 $n$ 的约数个数是（）。

（1 分）

$(a_1 + 1)(a_2 + 1) \cdots$ ——每个质因子的指数从 $0$ 到 $a_i$ 独立取值

$a_1 + a_2 + \cdots$

$n$

$p_1 \times p_2 \times \cdots$

第 56 题 E4 未作答

$72 = 2^3 \times 3^2$ ，约数个数是（）。

（1 分）

$6$

$5$

$72$

$12$

第 57 题 E5 未作答

若 $n = p^a$ （单质因子），约数和是（）。

（1 分）

$p \times a$

$1 + p + p^2 + \cdots + p^a$ （等比数列求和）

$p^a$

$a$

第 58 题 E6 未作答

$8 = 2^3$ ，约数和 $1 + 2 + 4 + 8 = ?$ （）。

（1 分）

$16$

$15$

$10$

$8$

第 59 题 E7 未作答

完全数是指等于其所有真约数（不含自身）之和的数。 $6 = 1 + 2 + 3$ ，下一个完全数是（）。

（1 分）

$12$

$10$

$20$

$28$

第 60 题 E8 未作答

$n > 1$ 的最小约数和最大约数分别是（）。

（1 分）

$1$ 和 $n-1$

都是 $n$

$1$ 和 $n$

$2$ 和 $n$

第 61 题 E9 未作答

求 $36$ 的所有约数时，枚举 $i$ 从 $1$ 到 $\sqrt{36} = 6$ ： $i$ 整除 $36$ 时 $i$ 和 $36/i$ 是一对约数。共找到约数（）个。

（1 分）

$18$

$9$

$36$

$6$

第 62 题 E10 未作答

枚举约数只需到 $\sqrt{n}$ ，原因是（）。

（1 分）

大于 $\sqrt{n}$ 的数不是约数

习惯如此

节省内存

约数成对出现： $i \times (n/i) = n$ ，找到小的一半就能推出大的一半

第 63 题 E11 未作答

约数个数为奇数的数是（）。

（1 分）

完全平方数——有一对约数 $i = n/i = \sqrt{n}$ 重合为一个

所有素数

所有偶数

所有奇数

第 64 题 E12 未作答

关于约数，错误的是（）。

（1 分）

素数恰好有 $2$ 个约数

$1$ 是所有正整数的约数

约数个数可由质因数分解计算

$n$ 的约数个数一定少于 $n$

陆

最大公约数与最小公倍数

12 QUESTIONS · 2 POINTS EACH

第 65 题 F1 未作答

$\gcd(a, b)$ （最大公约数）的定义是（）。

（1 分）

$a$ 和 $b$ 中较大的那个

$a \times b$

同时整除 $a$ 和 $b$ 的最大正整数

$a$ 和 $b$ 的和

第 66 题 F2 未作答

辗转相除法（欧几里得算法）的原理是 $\gcd(a, b) = \gcd(b, a \bmod b)$ 。其正确性依据是（）。

（1 分）

只适用于偶数

$a$ 和 $b$ 的公因数与 $b$ 和 $a \bmod b$ 的公因数完全相同—— $a = qb + r$ 中，整除 $a$ 和 $b$ 的数必整除 $r = a - qb$

数学归纳法

运气好

第 67 题 F3 未作答

辗转相除法的递归代码是（）。

（1 分）

int gcd(int a, int b) { return a + b; }

int gcd(int a, int b) { return a - b; }

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int gcd(int a, int b) { return a * b; }

第 68 题 F4 未作答

gcd 递归中 b == 0 时返回 a，原因是（）。

（1 分）

没有原因

任何数整除 $0$ ，所以此时的 $a$ 就是最大公约数

$a$ 是最小值

$a$ 一定是 $0$

第 69 题 F5 未作答

gcd 的迭代（非递归）写法是（）。

（1 分）

while (b) { int t = a % b; a = b; b = t; } return a;

return a + b;

for (int i = 1; i <= a; ++i) if (a % i == 0 && b % i == 0) ans = i;

while (a) { int t = b % a; b = a; a = t; } return b;

第 70 题 F6 未作答

$\gcd(319, 377)$ 用辗转相除法计算： $377 = 1 \times 319 + 58$ ， $319 = 5 \times 58 + 29$ ， $58 = 2 \times 29 + 0$ 。结果是（）。（2019 年真题）

（1 分）

$58$

$31$

$29$

$27$

第 71 题 F7 未作答

$\text{lcm}(a, b)$ （最小公倍数）的定义是（）。

（1 分）

$a + b$

$a$ 和 $b$ 中较小的

同时被 $a$ 和 $b$ 整除的最小正整数

$a$ 和 $b$ 的乘积

第 72 题 F8 未作答

$\gcd(a, b) \times \text{lcm}(a, b) = ?$ （）。

（1 分）

$a \times b$

$a + b$

$\gcd(a, b)$

$1$

第 73 题 F9 未作答

$\text{lcm}(12, 18)$ 的值是（）。

（1 分）

$216$

$6$

$12$

$36$

第 74 题 F10 未作答

$\gcd(a, a) = ?$ （）。

（1 分）

$a$

$1$

$2a$

$a^2$

第 75 题 F11 未作答

更相减损法（中国古代算法）用减法代替取模： $\gcd(a, b) = \gcd(b, a - b)$ （ $a > b$ ）。它比辗转相除法（）。

（1 分）

更快

可能更慢——连续减很多次才等价于一次取模（如 $\gcd(1000, 1)$ 需减 $999$ 次）

结果不同

没有区别

第 76 题 F12 未作答

两个数的 $\gcd = 6$ 、 $\text{lcm} = 36$ ，这两个数的乘积是（）。

（1 分）

$216$

$36$

$42$

$6$

柒

同余与取模应用

12 QUESTIONS · 2 POINTS EACH

第 77 题 G1 未作答

$a \equiv b \pmod{m}$ 的含义是（）。

（1 分）

$a$ 等于 $b$

$a$ 大于 $b$

$a + b = m$

$a$ 和 $b$ 除以 $m$ 的余数相同（即 $m$ 整除 $a - b$ ）

第 78 题 G2 未作答

若 $a \equiv b \pmod{m}$ 且 $c \equiv d \pmod{m}$ ，则 $a + c \equiv ? \pmod{m}$ （）。

（1 分）

$b - d$

$b \times d$

$b + d + m$

$b + d$

第 79 题 G3 未作答

若 $a \equiv b \pmod{m}$ 且 $b \equiv c \pmod{m}$ ，则（）。

（1 分）

$a \equiv c \pmod{m}$

无法判断

$a + c \equiv 0$

$a != c$

第 80 题 G4 未作答

天干 $10$ 个、地支 $12$ 个。公历年份 $Y$ 的天干索引 $= Y \bmod 10$ 、地支索引 $= Y \bmod 12$ 。 $2024$ 年的天干索引和地支索引分别是（）。（2020 年真题考法）

（1 分）

$0$ 和 $0$

$4$ 和 $8$

$0$ 和 $4$

$4$ 和 $4$

第 81 题 G5 未作答

数列 $0, 1, 2, 3, 0, 1, 2, 3, \ldots$ （周期为 $4$ ）的第 $n$ 项（从 $0$ 开始）是（）。

（1 分）

$n / 4$

$n \bmod 4$

$n$

$0$

第 82 题 G6 未作答

$f[n] = (f[n-1] + f[n-2]) \% 7$ ， $f[0] = f[1] = 1$ 。此数列 $\bmod 7$ 的周期（Pisano 周期）是 $16$ 。 $f[2025] = f[?]$ （）。（2025 年真题考法）

（1 分）

$f[2025]$

$f[2025 \bmod 7] = f[6]$

$f[16]$

$f[2025 \bmod 16] = f[9] = 6$

第 83 题 G7 未作答

计算 $a^n \bmod m$ （ $n$ 很大）时，朴素方法一个一个乘会超时。标准优化是（）。

（1 分）

无法优化

算完 $a^n$ 再取模

快速幂：利用 $a^{2k} = (a^k)^2 \bmod m$ ，每次平方把指数减半—— $O(\log n)$

用浮点数

第 84 题 G8 未作答

编程中递推取模（如 $f[i] = (f[i-1] + f[i-2]) \% M$ ）的主要目的是（）。

（1 分）

防止数值溢出——结果始终在 $[0, M-1]$ 内，long long 不会溢出

提高速度

使结果更精确

节省内存

第 85 题 G9 未作答

判断" $a$ 和 $b$ 除以 $m$ 余数是否相同"，正确的代码是（）。

（1 分）

a + b == m

a == b

a / m == b / m

a % m == b % m

第 86 题 G10 未作答

哈希函数中用取模（ $\text{hash}(x) = x \bmod M$ ）的目的是（）。

（1 分）

加密数据

求最大公约数

把任意大的数映射到固定范围 $[0, M-1]$ 内作为数组下标

排序

第 87 题 G11 未作答

同余方程 $x \equiv 3 \pmod{5}$ 的解是（）。

（1 分）

$x = 3, 8, 13, 18, \ldots$ （所有形如 $5k + 3$ 的数）

$x = 5$

只有 $x = 3$

无解

第 88 题 G12 未作答

$(7^2) \bmod 5 = ?$ （）。

（1 分）

$2$

$0$

$4$

$9$

捌

综合与易错

12 QUESTIONS · 2 POINTS EACH

第 89 题 H1 未作答

关于整除与模运算，错误的是（）。

（1 分）

$C++$ 中整数除法向零截断

$a \bmod b$ 的结果在 $[0, b-1]$ 内（ $a \ge 0$ ）

取模满足分配律

$-7 \% 3$ 在 C++ 中结果为 $2$

第 90 题 H2 未作答

关于素数判定，错误的是（）。

（1 分）

$2$ 是唯一的偶素数

$1$ 是最小的素数

$97$ 是 $100$ 以内最大的素数

试除到 $\sqrt{n}$ 即可

第 91 题 H3 未作答

关于筛法，错误的是（）。

（1 分）

线性筛保证每个合数只被标记一次

埃氏筛复杂度 $O(n \log \log n)$

线性筛复杂度是 $O(n \log n)$

埃氏筛从每个素数的平方开始标记

第 92 题 H4 未作答

下列关于 $1$ 的说法正确的是（）。

（1 分）

$1$ 是合数

$1$ 是素数

$1$ 是唯一的素数

$1$ 既不是素数也不是合数

第 93 题 H5 未作答

所有偶数中是素数的只有（）。

（1 分）

没有偶素数

$2$

所有偶数都是素数

$0$

第 94 题 H6 未作答

C++ 表达式 7 % 3 + 1 的值是（）。

（1 分）

$2$

$0$

$3$

$1$

第 95 题 H7 未作答

分解 $100$ ：先用 $2$ 除尽两次得 $25$ ；再用 $3$ 除不尽、 $4$ 不是素数跳过、 $5$ 除尽两次得 $1$ 。分解为 $100 = 2^2 \times 5^2$ 。如果分解完循环后剩余 $n > 1$ ，说明（）。

（1 分）

不需要处理

$n$ 是合数需要继续

分解失败

剩余的 $n$ 本身是素数（没有 $\le \sqrt{n}$ 的因子），要作为最后一个质因子输出

第 96 题 H8 未作答

C++ 中 $-13 \% 5$ 的结果是（）。

（1 分）

$-2$

$3$

$-3$

$2$

第 97 题 H9 未作答

$100$ 以内的素数中，十位数字为 $9$ 的是（）。

（1 分）

$97$ （ $91 = 7 \times 13$ 是合数）

$91$ 和 $97$

$90$ 和 $97$

只有 $97$

第 98 题 H10 未作答

$\gcd(24, 36) = 12$ ， $\text{lcm}(24, 36) = ?$ （）。

（1 分）

$12$

$864$

$72$

$24$

第 99 题 H11 未作答

$N = 2^5 \times 3^3$ ， $N$ 的约数个数是（）。

（1 分）

$24$

$15$

$216$

$8$

第 100 题 H12 未作答

关于数论基础，错误的是（）。

（1 分）

辗转相除法求 gcd 是 $O(\log)$ 级

约数个数可由质因数分解计算

唯一分解定理保证分解唯一

所有素数都是奇数

玖

真题演练

6 QUESTIONS · 真题演练不计分

第 1 题单选未作答

$100$ 以内最大的素数是（）。

（0 分）

$89$

$93$

$91$

$97$

CSP-J 2019 · 单选第9题｜知识点质数判定、初等代数

第 2 题单选未作答

$319$ 和 $377$ 的最大公约数是（）。

（0 分）

$29$

$33$

$31$

$27$

CSP-J 2019 · 单选第10题｜知识点最大公约数、质因数分解

第 3 题单选未作答

干支纪年法是中国传统的纪年方法，由 $10$ 个天干和 $12$ 个地支组合成 $60$ 个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。

天干＝（公历年份）除以 $10$ 所得余数

地支＝（公历年份）除以 $12$ 所得余数

例如，今年是 $2020$ 年， $2020$ 除以 $10$ 余数为 $0$ ，查表为“庚”； $2020$ 除以 $12$ ，余数为 $4$ ，查表为“子”，所以今年是庚子年。

请问 $1949$ 年的天干地支是（）。

（0 分）

己酉

己亥

己丑

己卯

CSP-J 2020 · 单选第13题｜知识点同余与模运算、最小公倍数

第 108~113 题阅读程序（共 0 分）未作答

1  #include <iostream>
2  using namespace std;
3 
4  const int n = 100000;
5  const int N = n + 1;
6 
7  int m;
8  int a[N], b[N], c[N], d[N];
9  int f[N], g[N];
10 
11  void init()
12  {
13      f[1] = g[1] = 1;
14      for (int i = 2; i <= n; i++) {
15          if (!a[i]) {
16              b[m++] = i;
17              c[i] = 1, f[i] = 2;
18              d[i] = 1, g[i] = i + 1;
19          }
20          for (int j = 0; j < m && b[j] * i <= n; j++) {
21              int k = b[j];
22              a[i * k] = 1;
23              if (i % k == 0) {
24                  c[i * k] = c[i] + 1;
25                  f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
26                  d[i * k] = d[i];
27                  g[i * k] = g[i] * k + d[i];
28                  break;
29              }
30              else {
31                  c[i * k] = 1;
32                  f[i * k] = 2 * f[i];
33                  d[i * k] = g[i];
34                  g[i * k] = g[i] * (k + 1);
35              }
36          }
37      }
38  }
39 
40  int main()
41  {
42      init();
43 
44      int x;
45      cin >> x;
46      cout << f[x] << ' ' << g[x] << endl;
47      return 0;
48  }

假设输入的 x 是不超过 $1000$ 的自然数，完成下面的判断题和单选题：

108.

若输入不为 1，把第 $13$ 行删去不会影响输出的结果。（）

正确

错误

109.

第 $25$ 行的 f[i] / c[i * k] 可能存在无法整除而向下取整的情况。（）

正确

错误

110.

在执行完 init() 后，f 数组不是单调递增的，但 g 数组是单调递增的。（）

正确

错误

111.

init 函数的时间复杂度为（）。

$\Theta(n)$

$\Theta(n\log n)$

$\Theta(n\sqrt{n})$

$\Theta(n^2)$

112.

在执行完 init() 后，f[1]、f[2]、f[3] …… f[100] 中有（）个等于 $2$ 。

$23$

$24$

$25$

$26$

113.

当输入为 1000 时，输出为（）。

15 1340

15 2340

16 2340

16 1340

CSP-J 2021 · 阅读程序第28-33题｜知识点欧拉筛、约数个数、约数和

第 10 题单选未作答

已知 $f[0] = 1 , f[1] = 1$ ，并且对于所有 $n \geq 2$ 有 $f[n] = (f[n-1] + f[n-2]) \% 7$ 。那么 $f[2025]$ 的值是多少？（）

（0 分）

$2$

$4$

$5$

$6$

CSP-J 2025 · 单选第8题｜知识点埃氏筛、堆排序

第 117~122 题阅读程序（共 0 分）未作答

1 2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25 

 #include <algorithm> #include <cstdio> #include <cstring> inline int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } int main() { int n; scanf("%d", &n); int ans = 0; for (int i = 1; i <= n; ++i) { for (int j = i + 1; j <= n; ++j) { for (int k = j + 1; k <= n; ++k) { if (gcd(i, j) == 1 && gcd(j, k) == 1 && gcd(i, k) == 1) { ++ans; } } } } printf("%d\n", ans); return 0; }

117.

当输入为 2 时，程序并不会执行第 $16$ 行的判断语句。（）

正确

错误

118.

将第 $16$ 行中的 && gcd(i,k)==1 删去不会影响程序运行结果。

正确

错误

119.

当输入的 $n \ge 3$ 的时候，程序总是输出一个正整数。

正确

错误

120.

将第 $7$ 行的 gcd(b,a%b) 改为 gcd(a,a%b) 后，程序可能出现的问题是（）

输出的答案大于原答案

输出的答案小于原答案

程序有可能陷入死循环

可能发生整型溢出问题

121.

当输入为 8 的时候，输出为

37

42

35

25

122.

调用 gcd(36,42) 会返回

6

252

3

2

CSP-J 2025 · 阅读程序第16-21题｜知识点欧拉筛、归并排序

重置作答

专题 10 数论基础 · 复习强化

判 分 报 告

整除与模运算

素数与合数

素数筛法

质因数分解

约数

最大公约数与最小公倍数

同余与取模应用

综合与易错

真 题 演 练

打印

导出 HTML 子卷

判分报告

真题演练