辗转相除法
与素数筛

答案：B. 12

48%36=12, 36%12=0 → GCD=12。

考点：辗转相除法依据 gcd(a,b) = gcd(b, a%b)，不断把大数换小，直到余数为 0，此时上一步的除数就是最大公约数。

易错：把递推写成 gcd(a,b)=gcd(b,a/b)（丢掉了取余），或在余数为 1 时误以为已经结束。

答案：B. 24

GCD(6,8)=2, LCM=6/2×8=3×8=24。

考点：求最小公倍数优先使用公式 LCM(a,b) = a / GCD(a,b) * b，先除后乘兼顾正确性与安全性。

易错：直接算 6×8=48，或想当然地把较大的 8 当作 LCM。

答案：C. O(N log log N)

这是埃氏筛的经典复杂度，接近线性但略慢。

考点：每个质数 p 要划掉约 N/p 个数，把所有质数的 N/p 相加约为 N·ln ln N，这就是埃氏筛的经典复杂度。

易错：与线性筛的 O(N) 混淆，或误记成暴力枚举的 O(N²)。

答案：C

这是线性筛的核心，保证O(N)复杂度的关键。

考点：当 i 能被当前最小质因子 primes[j] 整除时立刻 break，可保证每个合数只被自己的最小质因子标记一次，这是 O(N) 的关键。

易错：以为 break 是为了跳过偶数或减少内存占用，误解了它「防止重复标记」的本意。

#include <iostream>
using namespace std;

int main() {
    int a = 1071, b = 462;             // 求 GCD(1071, 462)
    int steps = 0;

    while (b != 0) {                   // 余数不为 0 就继续
        int r = a % b;                 // 取余数
        cout << a << " / " << b << " = " << a / b
             << " 余 " << r << endl;
        a = b;                         // 除数变成被除数
        b = r;                         // 余数变成除数
        steps++;                       // 做了一次除法
    }

    cout << "共 " << steps << " 次除法，GCD = " << a << endl;   // 3 次，GCD = 21
    return 0;
}

答案：共 3 步除法，GCD(1071, 462) = 21。过程：1071 ÷ 462 = 2 余 147 → 462 ÷ 147 = 3 余 21 → 147 ÷ 21 = 7 余 0。

思路：辗转相除法（欧几里得算法）的核心性质是 gcd(a, b) = gcd(b, a mod b)。每做一次"a ÷ b 取余"，就把除数挪到被除数的位置、余数挪到除数的位置，直到余数变成 0，此时除数就是最大公约数。本题数了 3 次除法：1071/462、462/147、147/21，第三次余数为 0，循环结束，答案是 21。

考点：辗转相除法（欧几里得算法）的原理与实现、a % b 取余、循环不变式。

易错：① 数步数时要明白"最后余 0 的那次也算一次除法"，所以是 3 步不是 2 步；② 交换顺序不能写反：先 a = b 再 b = r，如果先写 b = r 就会把还需要的旧 b 覆盖掉（写成 int r = a % b; 提前存好余数就没问题）；③ 边界情况：若两个数中有 0，GCD 就是另一个数，此时循环一次都不执行，答案直接是 a。

答案：A. x=1, y=-1

GCD(12,8)=4。验证：12×1+8×(-1)=12-8=4 ✅

考点：扩展欧几里得算法在辗转相除求 GCD 的同时回推系数，给出一组满足 ax + by = gcd(a,b) 的整数解。

易错：把 x、y 当成 12 和 8 的因数（如 3 和 2），或忘记 x、y 中通常有一个是负数。

答案：D. 5

3×5=15≡1(mod 7)。或用EXGCD：exgcd(3,7,x,y)→x=-2→((-2%7)+7)%7=5。

考点：乘法逆元就是满足 a × x ≡ 1 (mod m) 的 x，模数很小时直接试乘 1~m-1 最快。

易错：把逆元当成 1/3 ≈ 0.33，或误用 7 - 3 = 4 之类与定义无关的计算。

答案：B. 19

[2,30]共29个数，质数10个(2,3,5,7,11,13,17,19,23,29)，合数=29-10=19。

考点：区间内合数个数可由「总数 − 质数个数」得到，而 [2,30] 中不含 1，所以总数就是 29 个。

易错：把 1 也算进合数，或漏数 29 导致质数个数算成 9 个。

答案：A（x=1, y=1）

GCD(6,9)=3, 15/3=5 → 有解。

A: 6+9=15 ✅; B: 12-9=3... 不对。重新验算：

B: 6×2+9×(-1)=12-9=3≠15 ❌

C: 6×(-1)+9×3=-6+27=21≠15 ❌

只有A正确，答案为 A。（注：此题需仔细验算每个选项）

考点：二元一次不定方程 ax+by=c 有整数解的充要条件是 gcd(a,b) 能整除 c，满足后再逐一验算选项即可。

易错：只验证一个选项就作答，或不知道一个解可加 (b/g, -a/g) 生成其他解而误判选项唯一。

答案：C. 2

j=0: 12×2=24, 标记。12%2==0 → break!

等等，12%2==0 在第一次就break了？那答案是C？

重新分析：12%2==0 → break，只用了质数2。

答案为 C. 2。

易错：以为内层循环会一直用质数表里的所有质数去筛，忽略 12 % 2 == 0 在第一次循环就触发 break。

答案：C. a×b

LCM = a/GCD(a,b)×b = a/1×b = a×b。互质时LCM等于乘积。

考点：把 LCM(a,b) = a / GCD(a,b) * b 中的 GCD 取 1，即得特例 LCM(a,b) = a × b。

易错：以为互质时 LCM 仍要再除以 2，或误把 LCM 当成 a + b。

答案：C

辗转相除法的时间复杂度是 O(log n)，不是 O(√n)。O(√n) 是试除法的复杂度。

考点：每做两次取模，新数值至少减半，所以辗转相除的步数与数的位数同阶，复杂度为 O(log n)。

易错：与试除法 O(√n) 混淆，或错记成埃氏筛的 O(N log log N)。