K02 数论、进制、位运算 + 高精度（第二轮系统课 · 第 2 次）

本次两个模块：

模块	内容	复用的旧讲义	本讲义新写
M3 数论、进制、位运算	取模、gcd/lcm、质数、分解质因数、筛法、k 进制、位运算	`S5` 第一节全部、`S1` 全部	lcm、分解质因数、线性筛、任意进制
M4 高精度	加、减、乘、除以小整数	`S6` 第一节（加法）	减法、乘法、除以小整数

⚠️ 订正 S5 的一句话：S5 末尾写"线性筛属于提高级"。查 2025 版大纲，入门级 2.1.5-3 明文写着"素数筛法：埃氏筛法与线性筛法"，所以线性筛也要会。本讲义 1.4 节补上。

一、M3 数论、进制、位运算

盲写（15 分钟，合上讲义）

写一个程序：输入 n（n ≤ 10⁶），输出 1~n 里质数的个数；再输入 a、b（≤ 10⁹），输出它们的最大公约数。

输入 100 换行 24 18 → 输出 25 换行 6

参考答案

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
bool notPrime[N];               // 全局数组，自动全是 false

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

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (notPrime[i]) continue;
        cnt++;
        for (long long j = 1LL * i * i; j <= n; j += i) notPrime[j] = true;   // i*i 可能超 int，用 long long
    }
    int a, b;
    cin >> a >> b;
    cout << cnt << endl << gcd(a, b) << endl;
    return 0;
}

写对了 → 只看下面的 ⚠️ 和新写的 1.2–1.5 节。写不出来 → 先把 S5 第一节读完，再回来。

1.1 复用：先翻旧讲义

内容	在哪
`%` 对负数、取模的两条性质	`S5` 1.1
辗转相除、约分	`S5` 1.2
质数判定（试到 √n）、埃氏筛	`S5` 1.3
位运算六个符号、三个必背写法、二进制转换	`S1` 第一节

1.2 最小公倍数

#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }   // 先除后乘

int main() {
    cout << lcm(4, 6) << endl;
    cout << lcm(1000000000, 999999999) << endl;
    return 0;
}

⚠️ 写成 a * b / gcd(a, b) 也对，但 a * b 那一步可能先溢出。 先除后乘，中间结果最小。

📝 一条常考的性质：gcd(a, b) × lcm(a, b) = a × b。

1.3 分解质因数（唯一分解定理）

每个大于 1 的整数都能唯一地写成质数的乘积，比如 360 = 2³ × 3² × 5。

怎么分解：从 2 开始试除，除得尽就一直除；试到 √n 为止，剩下的数如果大于 1，它本身就是一个质数。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    // n<=1e12，试除到 sqrt(n)=1e6，O(sqrt n) 能过
    long long divisors = 1;               // 顺便算因数个数
    bool first = true;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p != 0) continue;
        int e = 0;
        while (n % p == 0) { n /= p; e++; }
        cout << (first ? "" : " * ") << p << "^" << e;
        first = false;
        divisors *= (e + 1);
    }
    if (n > 1) {                          // 剩下的一定是质数
        cout << (first ? "" : " * ") << n << "^1";
        divisors *= 2;
    }
    cout << endl << divisors << endl;
    return 0;
}

⚠️ 三个坑：

循环条件写 p * p <= n，别写 p <= sqrt(n)——sqrt 返回小数，有精度误差；而且 n 在循环里一直变小，条件也跟着收紧，这是对的。
p * p 可能超 int，p 用 long long。
**最后那个 if (n > 1) 不能漏。**比如 97 是质数，循环里一次都除不尽，全靠这一句输出。

📝 因数个数公式：n = p₁^e₁ × p₂^e₂ × …，因数个数 = (e₁+1)(e₂+1)…。360 的因数个数 = 4 × 3 × 2 = 24。

1.4 线性筛

埃氏筛里，12 会被 2 划掉一次、又被 3 划掉一次，有重复。线性筛保证每个合数只被它的最小质因子划掉一次，所以是 O(n)。

#include <bits/stdc++.h>
using namespace std;

const int N = 10000005;
bool notPrime[N];
int primes[700000], cnt = 0;              // 1e7 以内质数约 66.5 万个

int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        if (!notPrime[i]) primes[cnt++] = i;
        for (int j = 0; j < cnt && 1LL * i * primes[j] <= n; j++) {
            notPrime[i * primes[j]] = true;
            if (i % primes[j] == 0) break;    // 关键一行：primes[j] 已经是 i 的最小质因子，再往后就重复了
        }
    }
    cout << cnt << endl;
    return 0;
}

📝 考试时埃氏筛就够用（n ≤ 10⁷ 时两种都能过）。线性筛要会写，是因为大纲要求、初赛也会考那一行 break 的作用。

1.5 任意进制转换

S1 讲了二进制。k 进制（2 ≤ k ≤ 16）的做法完全一样，只是把 2 换成 k，数字超过 9 的用字母表示。

#include <bits/stdc++.h>
using namespace std;

const string DIG = "0123456789ABCDEF";

// k 进制字符串 -> 十进制：从高位到低位，ans = ans * k + 这一位
long long toDec(string s, int k) {
    long long ans = 0;
    for (char c : s) ans = ans * k + DIG.find(c);
    return ans;
}

// 十进制 -> k 进制：不断除以 k 取余，余数倒着读
string fromDec(long long x, int k) {
    if (x == 0) return "0";                // 别漏了 0
    string s = "";
    while (x > 0) { s += DIG[x % k]; x /= k; }
    reverse(s.begin(), s.end());
    return s;
}

int main() {
    cout << toDec("FF", 16) << endl;
    cout << fromDec(255, 2) << endl;
    cout << fromDec(255, 8) << endl;
    cout << fromDec(0, 7) << endl;
    return 0;
}

⚠️ x == 0 要单独处理：不处理的话 while 一次都不进，返回空串。

1.6 位运算的一个经典用法：异或找落单

a ^ a = 0，a ^ 0 = a，而且异或满足交换律。 所以把一堆数全部异或起来，成对的都会抵消，只剩下落单的那个。不用开数组。

这正好是课堂题 P1469 找筷子：n 最大 10⁷，内存限制只有 8 MB。10⁷ 个 int 要 40 MB——K01 1.1 那张内存表在这里直接决定生死。

二、M4 高精度

盲写（15 分钟，合上讲义）

输入两个非负整数 a、b（各最多 500 位），输出 a + b。

输入 99999999999999999999 换行 1 → 输出 100000000000000000000

参考答案就是 S6 第一节的代码，写完自己去对。

高精度的三步（S6 那句话）：倒着存进数组 → 逐位算 + 处理进位/借位 → 倒着打印。 下面三种运算只换中间那一步。

下面统一用 vector<int> 存数字，下标 0 是个位。

2.1 减法（a ≥ b）

#include <bits/stdc++.h>
using namespace std;

vector<int> toVec(const string& s) {          // "123" -> {3,2,1}
    vector<int> v;
    for (int i = s.size() - 1; i >= 0; i--) v.push_back(s[i] - '0');
    return v;
}

void print(vector<int> v) {
    while (v.size() > 1 && v.back() == 0) v.pop_back();   // 去掉前导零，但至少留一位
    for (int i = v.size() - 1; i >= 0; i--) cout << v[i];
    cout << endl;
}

// 比较两个非负大数：a < b 返回 true
bool less_(const string& a, const string& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;                              // 等长时字典序就是数值大小
}

vector<int> sub(vector<int> a, const vector<int>& b) {   // 要求 a >= b
    for (int i = 0; i < (int)a.size(); i++) {
        if (i < (int)b.size()) a[i] -= b[i];
        if (a[i] < 0) { a[i] += 10; a[i + 1]--; }          // 借位
    }
    return a;
}

int main() {
    string x, y;
    cin >> x >> y;
    if (less_(x, y)) { cout << "-"; swap(x, y); }         // 小减大：先输出负号，再反过来减
    print(sub(toVec(x), toVec(y)));
    return 0;
}

⚠️ 三个坑：①先比大小，小减大要交换并补负号；②字符串比大小要先比长度，"9" > "10" 在字典序里是真的；③去前导零时至少留一位，否则 123 - 123 什么都不输出。

⚠️ 这里的 less_(x, y) 假设输入没有前导零（题目一般保证）。

2.2 乘法（高精 × 高精）

a 的第 i 位乘 b 的第 j 位，结果加到第 i + j 位上。最后统一进位。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string x, y;
    cin >> x >> y;
    int la = x.size(), lb = y.size();
    vector<int> a(la), b(lb), c(la + lb, 0);      // 积最多 la+lb 位
    for (int i = 0; i < la; i++) a[i] = x[la - 1 - i] - '0';
    for (int i = 0; i < lb; i++) b[i] = y[lb - 1 - i] - '0';

    for (int i = 0; i < la; i++)
        for (int j = 0; j < lb; j++)
            c[i + j] += a[i] * b[j];               // 先全部累加，不急着进位

    for (int k = 0; k + 1 < la + lb; k++) {        // 统一进位
        c[k + 1] += c[k] / 10;
        c[k] %= 10;
    }
    int top = la + lb - 1;
    while (top > 0 && c[top] == 0) top--;          // 去前导零，至少留一位
    for (int k = top; k >= 0; k--) cout << c[k];
    cout << endl;
    return 0;
}

⚠️ 乘以 0 的时候，结果是一串 0，去前导零后必须剩一个 0——第二组样例就是查这个的。P1303 A*B 有同学卡在 40 分，常见原因就是这一步和数组开小。

2.3 除以小整数（高精 ÷ int）

除法和前三种相反，从高位往低位算，就像竖式除法：

#include <bits/stdc++.h>
using namespace std;

int main() {
    string x;
    long long b;                       // 除数不超过 1e9
    cin >> x >> b;
    string q = "";
    long long r = 0;                   // r*10 + 一位，最大约 1e10，要 long long
    for (char ch : x) {                // 从最高位开始
        r = r * 10 + (ch - '0');
        q += char('0' + r / b);
        r %= b;
    }
    int p = 0;
    while (p + 1 < (int)q.size() && q[p] == '0') p++;   // 去前导零，至少留一位
    cout << q.substr(p) << endl << r << endl;           // 商、余数
    return 0;
}

📝 四种运算的方向：加、减、乘从低位往高位（进位往高处走）；除从高位往低位（余数往低处走）。

三、课堂题与小测

环节	题目	要点
课堂题 1	P1469 找筷子（橙）	先看内存限制，再决定写法；n 到 10⁷，读入用 `scanf`
课堂题 2	P1075 质因数分解（橙）	n 最大多少？试除到哪里就够？
课堂题 3	P1480 A/B Problem（橙）	就是 2.3 节
小测 1（20 分钟）	P1029 最大公约数和最小公倍数问题（橙）	枚举什么？范围多大？（K01 枚举三问）
小测 2（20 分钟）	*P1303 AB Problem**（橙）	自造数据必须包含"乘以 0"

四、课后作业

档	必做（4 道）	选做
B 档	① P1143 进制转换（橙） ② P1217 回文质数（橙） ③ P1601 高精度加法（橙） ④ P2142 高精度减法（橙）	P1062 数列（橙，进制思想）
A 档	① P1217 回文质数（橙，数据范围决定先筛还是先造回文数） ② P1017 进制转换（橙，负进制） ③ P1835 素数密度（黄，区间很大但长度不大） ④ P1045 麦森数（黄，高精度乘法 + K03 的快速幂）	P1062 数列（橙）

五、30 秒自测

lcm(a, b) 为什么写成 a / gcd(a, b) * b？
分解质因数的循环结束后，为什么还要判断 if (n > 1)？
线性筛里 if (i % primes[j] == 0) break; 这一行起什么作用？
高精度减法前，为什么要先比大小？字符串怎么比大小？
高精度乘法，结果数组最多开几位？乘以 0 要注意什么？
高精度除以小整数，从哪一位开始算？

答案

先除后乘，中间结果不会先溢出。
试除到 √n 后，剩下的数如果大于 1，它本身就是一个质因数（最多只有一个）。
保证每个合数只被它的最小质因子筛掉一次，所以是 O(n)。
按"大减小"写的借位逻辑，小减大会借穿；先比长度，长度相同再按字典序比。
la + lb 位；去前导零时至少留一位 0。
从最高位开始，余数乘 10 加下一位。

本次打卡：M3 ①、M4 ①（两道盲写）；作业 AC 后打 ②③。