Day7 数论选择与阅读（重制版·12题）

范围：整除、gcd/lcm、同余、质数与筛法；先判断性质，再进行计算。

一、数论基础

---

第 1 题

$\gcd(252,198)$ 的值是（ {{ select(1) }} ）。

• $6$
• $9$
• $18$
• $36$

---

第 2 题

$\operatorname{lcm}(84,126)$ 的值是（ {{ select(2) }} ）。

• $126$
• $168$
• $252$
• $504$

---

第 3 题

$3^{2026}\bmod 7$ 的值是（ {{ select(3) }} ）。

• $1$
• $2$
• $3$
• $4$

---

第 4 题

满足 $x\equiv4\pmod 6$ 且 $x\equiv6\pmod 8$ 的最小正整数 $x$ 是（ {{ select(4) }} ）。

• $10$
• $14$
• $22$
• $46$

---

第 5 题

$360=2^3\times3^2\times5$ 的正因数个数是（ {{ select(5) }} ）。

• $12$
• $18$
• $24$
• $30$

---

第 6 题

不超过 $50$ 的质数共有（ {{ select(6) }} ）。

• $13$
• $14$
• $15$
• $16$

---

第 7 题

埃氏筛在处理质数 $i$ 时通常从 $i^2$ 开始标记，主要原因是（ {{ select(7) }} ）。

• 小于 $i^2$ 的合数若含因数 $i$，已经被更小的质因数处理过
• 从 $2i$ 开始会漏掉 $i^2$
• $i^2$ 一定是第一个合数
• 这样可以把空间复杂度降为 $O(1)$

---

二、阅读程序

---

程序：整体 gcd、整体 lcm 与互质数对

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (long long &x : a) cin >> x;

    long long g = a[0], l = a[0];
    for (int i = 1; i < n; ++i) {
        g = gcd(g, a[i]);
        l = l / gcd(l, a[i]) * a[i];
    }

    int cnt = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (gcd(a[i], a[j]) == 1) ++cnt;

    cout << g << " " << l << " " << cnt;
    return 0;
}

第 8 题

输入 4 6 10 15 21 时，程序输出（ {{ select(8) }} ）。

• 1 210 1
• 1 630 1
• 2 210 5
• 1 210 5

---

第 9 题

对上述输入，第一次循环结束后变量 g 和 l 分别为（ {{ select(9) }} ）。

• 1 和 210
• 2 和 210
• 1 和 630
• 6 和 21

---

第 10 题

若把 gcd(a[i], a[j]) == 1 改为 gcd(a[i], a[j]) > 1，上述输入的 cnt 为（ {{ select(10) }} ）。

• $1$
• $3$
• $5$
• $6$

---

第 11 题

当 $n=4$ 时，程序显式调用 gcd 的总次数是（ {{ select(11) }} ）。

• $6$
• $7$
• $9$
• $12$

---

第 12 题

计算 lcm 时先执行除法再执行乘法，最主要的好处是（ {{ select(12) }} ）。

• 保证结果一定不超过 int 范围
• 减小中间乘积，降低溢出风险
• 把时间复杂度降为 $O(1)$
• 避免调用 gcd

---