🎮 算法篇第一章 整数理论大冒险 🍎

一、趣味开场（导入）

想象一下，你有 12 个苹果，想要请同学们一起吃。你把苹果一人一个地往外发：

😊 2人分: 每人 6 个 (✔) 😃 3人分: 每人 4 个 (✔) 😅 5人分: 剩 2 个 (❌)

这时候，你脑子里其实已经在做一件事——判断某个数能不能“整整齐齐地分掉另一个数”，这就是“整除”和“约数”的世界啦。

再想象你在玩一个“敲鼓游戏”：地上写着好多数字，每当你喊出一个数它的“倍数小弟”都要站出来。比如你喊“3”，地上写着的 3、6、9、12 都要啪啪站起来。

“约数”“倍数”“质数”这些听起来有点严肃的词，其实就是在玩这种“谁能整谁”的游戏。

还有一个场景：体育老师让大家排队报数，报到 2 和 5 的要做俯卧撑。你会发现有的同学要做很多次，因为他既是 2 的倍数又是 5 的倍数。这背后其实就在考你：哪些数是“好朋友”（公因数），哪些数是“共同生日”（最大公约数、最小公倍数）。

今天这节课，我们就来做一件酷酷的事——用 C++14 来玩“整数理论”的游戏：分苹果、数约数、找质数、算最大公约数、最小公倍数……听起来就很像一整套奥数 + 编程的组合拳，对吧？😎

二、知识点讲解

知识点 1：整除与约数

1. 白话定义

有两个整数 a 和 b，如果可以找到一个整数 q，让 b = a × q，那就说 “a 能整除 b”，记作 a | b。

这时候：

2. 生活类比

我们常常会问的问题：“x 个人来分 n 个苹果，能不能分得刚刚好？”其实就是在问：x 是不是 n 的约数。

3. 小小性质

4. C++14 示例：判断能不能平均分

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

int main() {
    int n, x;
    cin >> n >> x;          // 输入苹果数 n 和人数 x
    if (n % x == 0) {       // 如果 n 能被 x 整除
        cout << "YES\n";    // 能平均分
    } else {
        cout << "NO\n";     // 分不均匀
    }
    return 0;
}

知识点 2：用 √n 优化找约数（枚举约数）

1. 白话思路

想要找到一个数 n 的所有约数，最笨的办法是：从 1 一直试到 n，看谁能整除它。

但我们发现：约数是成对出现的：如果 k 是 n 的约数，那 n / k 也是 n 的约数。

120 的约数配对 1 120 2 60 ... 只需要找这边 (√n)

例如 120：1 ↔ 120, 2 ↔ 60, 10 ↔ 12... 所以只要枚举到 k * k <= n（也就是 k <= √n）就够了，每找到一个约数 k，就可以顺便得到另一个约数 n / k。

2. 类比

想象你在找“身高配对”：规定两个人身高乘积是 120。如果你找到一个 4cm 的“小积木人”，另一个“搭档”一定是 30cm。你只需要往上找，找到一半（约 √120）就可以把所有搭档找完。

3. C++14 示例：找出所有约数并存进数组

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

// 把 n 的所有约数存到 vector 里，并按从小到大排序
vector<int> get_divisors(int n) {
    vector<int> d;
    for (int k = 1; k * k <= n; ++k) {   // 只枚举到 sqrt(n)
        if (n % k == 0) {               // 找到一个约数 k
            d.push_back(k);             // 加入 k
            if (k * k != n) {           // 如果另一半不是同一个数
                d.push_back(n / k);     // 再加上 n / k
            }
        }
    }
    sort(d.begin(), d.end());           // 排序，变成从小到大
    return d;
}

int main() {
    int n;
    cin >> n;
    vector<int> d = get_divisors(n);
    cout << "约数个数 = " << d.size() << "\n";
    cout << "所有约数：";
    for (int x : d) cout << x << " ";
    cout << "\n";
    return 0;
}

知识点 3：质数与合数 + 判断质数

1. 白话定义

一个大于等于 2 的整数：

重要结论：如果 a 是合数，那一定可以写成 a = p × q，并且至少有一个质因子 p ≤ √a。所以判断一个数是不是质数，只需要试所有 2 ≤ i ≤ √a，如果都不能整除，就可以认定它是质数。

2. 类比

想象你在检查一块“乐高砖块”是不是“基本砖块”：如果它可以拆成两块更小的整数长度砖块，那它是“合体砖”（合数）；如果拆不开，只能是 1 和它自己，那就是“质数砖”。

3. C++14 示例：判断一个数是否是质数

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

bool is_prime(int x) {
    if (x < 2) return false;              // 小于 2 的不是质数
    for (int i = 2; i * i <= x; ++i) {    // 只试到 sqrt(x)
        if (x % i == 0) return false;     // 找到能整除的，说明是合数
    }
    return true;                          // 没找到约数，就是质数
}

int main() {
    int n;
    cin >> n;
    if (is_prime(n)) cout << "Prime\n";
    else cout << "Not prime\n";
    return 0;
}

知识点 4：埃拉托斯特尼筛法（素数筛）

1. 白话思路

要找 1 到 N 之间所有的质数，一个个用 is_prime 判断会有点慢。

更聪明的做法：

  1. 一开始假装 2～N 都是质数；
  2. 从 2 开始，把它的倍数统统划掉（因为它们一定有约数 2，是合数）；
  3. 再找下一个没被划掉的数 3，把 3 的倍数划掉……
  4. 最后没有被划掉的，就是质数。
1 2 3 4 5 6 7 8 9 划掉 2 的倍数... 划掉 3 的倍数... 剩下的红圈就是质数！

2. C++14 示例：筛出 1～N 之间所有质数

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

const int MAXN = 1000000;   // N 的最大可能值
bool is_composite[MAXN + 1]; // false 表示暂时认为是质数

int main() {
    int N;
    cin >> N;

    is_composite[0] = is_composite[1] = true; // 0 和 1 不是质数

    for (int i = 2; i * i <= N; ++i) {
        if (!is_composite[i]) {              // i 还是质数
            for (int j = i * i; j <= N; j += i) {
                is_composite[j] = true;      // j 是 i 的倍数，所以是合数
            }
        }
    }

    cout << "1~" << N << " 之间的质数有：\n";
    for (int i = 2; i <= N; ++i) {
        if (!is_composite[i]) cout << i << " ";
    }
    cout << "\n";
    return 0;
}

进阶：图片里还给出了“区间筛”的版本，可以统计 [L,R] 中有多少个质数。思想是：先筛出所有不超过 √R 的质数，再在 [L,R] 这段小区间上划掉它们的倍数。

知识点 5：最大公约数 GCD 和最小公倍数 LCM

1. 白话定义

2. 生活类比：木棍问题

有两根木棍，分别长 10cm 和 16cm。

3. 欧几里得算法（辗转相除法）

计算 gcd 的超好用公式：gcd(x, y) = gcd(y, x % y)

例：gcd(18, 12)
18 % 12 = 6 → gcd(18,12) = gcd(12,6)
12 % 6 = 0 → gcd(12,6) = 6
所以 gcd(18,12) = 6。

4. C++14 示例：gcd + lcm

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

// 欧几里得算法，递归写法
int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y); // y 为 0 时，x 就是答案
}

long long lcm(long long a, long long b) {
    // 先求最大公约数，再用 a*b/gcd 得到最小公倍数
    return a / gcd(a, b) * b;          // 先除后乘，减少溢出风险
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << "gcd = " << gcd(a, b) << "\n";
    cout << "lcm = " << lcm(a, b) << "\n";
    return 0;
}

知识点 6（进阶）：“拍头”与贡献法 —— 统计倍数个数

1. 题目大意

有 n 个正整数排成一排，每个数头上写着一个值。对于每个数 a[i]，我们想知道：它是另外多少个数的倍数。

2. 换个角度：贡献法

贡献法思路：

  1. 先统计：每个数值 x 在数组里出现了多少次，记为 c[x]。
  2. 然后，对于每个数值 i，把它的出现次数 c[i] 统统“传给”它的所有倍数 j（2i, 3i, 4i ...），对每个 j 加上 c[i]。
  3. 最后，对于数值 v，它头上的计数 w[v] 就表示：数组中有多少个数是它的约数。
  4. 减掉自己：答案是 w[a[i]] - 1。

3. 简化版 C++14 示例（核心循环）

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

const int MAXV = 1000000;  // 数值上限

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    static int cnt[MAXV + 1], w[MAXV + 1];

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];          // 读入原数组
        cnt[a[i]]++;          // 统计每个值出现次数
    }

    // 对每个可能的数 i，把它向所有倍数 j 传递“出现次数”的贡献
    for (int i = 1; i <= MAXV; ++i) {
        if (cnt[i] == 0) continue;      // 这个数根本没出现，就跳过
        for (int j = i; j <= MAXV; j += i) {
            w[j] += cnt[i];             // i 会给它所有倍数 j 做贡献
        }
    }

    // 输出每个 a[i] 的答案：它是另外多少个数的倍数
    for (int i = 1; i <= n; ++i) {
        cout << w[a[i]] - 1 << " ";     // 减掉自己那一次
    }
    cout << "\n";
    return 0;
}

三、常见题型总结（面向 CSP-J）

题型 1：整除判断 & 平均分
核心：判断 a % b == 0。
坑点：忘记 b > a 的情况；Yes/NO 大小写错误。
题型 2：约数枚举
核心：√n 优化。
坑点：k * k == n 时重复计算；数组下标搞混。
题型 3：质数相关
核心：is_prime 或 筛法。
坑点：把 1 当质数；循环范围写错导致超时。
题型 4：GCD / LCM
核心：欧几里得算法。
坑点：乘法爆 int (用 long long)；递归死循环。
题型 5：倍数统计 (进阶)
核心：贡献法 (O(n log n))。
坑点：双重循环超时；没减掉“自己”。

四、课堂练习题 ✍️

下面 6 道练习题，从简单到进阶，请动手写一写吧！

练习 1：能不能平均分？（整除判断）

题目描述：小明带来了一大袋苹果，一共有 n 个。现在有 x 个同学来一起吃。每个同学必须得到一样多的苹果，而且不能切半个苹果。请你帮老师判断：这袋苹果能不能平均分给这 x 个同学？

输入：两个正整数 n 和 x。
输出：可以平均分输出 YES，否则输出 NO。

样例 1： 输入 12 3 → 输出 YES
样例 2： 输入 12 5 → 输出 NO
查看参考代码 (C++14) 
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n, x;
    cin >> n >> x;
    if (n % x == 0) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}
练习 2：苹果可以怎么分？（枚举约数）

题目描述：有多少种人数 x 可以把 n 个苹果分得刚刚好？请输出种类数和所有的 x（从小到大）。

样例 1： 输入 12 → 输出 6 (换行) 1 2 3 4 6 12
查看参考代码 (C++14) 
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n;
    cin >> n;
    vector<long long> d;
    for (long long k = 1; k * k <= n; ++k) {
        if (n % k == 0) {
            d.push_back(k);
            if (k * k != n) d.push_back(n / k);
        }
    }
    sort(d.begin(), d.end());
    cout << d.size() << "\n";
    for (long long x : d) cout << x << " ";
    cout << "\n";
    return 0;
}
练习 3：最小循环节（字符串版约数应用）

题目描述：给你一个字符串 s，问它是不是由一个更短的小串重复若干次拼成的？输出最短的小串长度。

样例 1： 输入 abbaabbaabba → 输出 4
查看思路与代码

思路：枚举长度 n 的所有约数 len，检查 s[i] == s[i % len]。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = (int)s.size();
    for (int len = 1; len <= n; ++len) {
        if (n % len == 0) { // 必须是约数
            bool ok = true;
            for (int i = 0; i < n; ++i) {
                if (s[i] != s[i % len]) {
                    ok = false; break;
                }
            }
            if (ok) {
                cout << len << "\n";
                return 0;
            }
        }
    }
    return 0;
}
练习 4：拍头游戏（倍数统计）

题目描述：n 个小朋友，每人有个数字 a[i]。问每个人：自己是另外多少个人的倍数？

样例 1： 输入 5 / 2 1 2 3 4 → 输出 2 0 2 1 3
查看参考代码 (贡献法) 
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1000000;
int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    static int cnt[MAXV + 1], w[MAXV + 1];
    int maxVal = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i]; cnt[a[i]]++; maxVal = max(maxVal, a[i]);
    }
    for (int i = 1; i <= maxVal; ++i) {
        if (cnt[i] == 0) continue;
        for (int j = i; j <= maxVal; j += i) w[j] += cnt[i];
    }
    for (int i = 1; i <= n; ++i) cout << w[a[i]] - 1 << (i < n ? " " : "");
    cout << "\n";
    return 0;
}
练习 5：1～N 之间有多少质数？

题目描述：求 1 到 N 之间所有质数的个数，并输出它们。

样例： 输入 10 → 输出 4 (换行) 2 3 5 7
查看参考代码 (筛法) 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
bool is_composite[MAXN + 1];
int main() {
    int N;
    cin >> N;
    is_composite[0] = is_composite[1] = true;
    for (int i = 2; i * i <= N; ++i) {
        if (!is_composite[i]) {
            for (int j = i * i; j <= N; j += i) is_composite[j] = true;
        }
    }
    vector<int> primes;
    for (int i = 2; i <= N; ++i) if (!is_composite[i]) primes.push_back(i);
    cout << primes.size() << "\n";
    for (int x : primes) cout << x << " ";
    cout << "\n";
    return 0;
}
练习 6：木棍大作战（GCD & LCM）

题目描述：给两个数 a 和 b，求它们的最大公约数和最小公倍数。

样例： 输入 10 16 → 输出 2 (换行) 80
查看参考代码 
#include <bits/stdc++.h>
using namespace std;
long long gcd_ll(long long x, long long y) {
    return y == 0 ? x : gcd_ll(y, x % y);
}
int main() {
    long long a, b;
    cin >> a >> b;
    long long g = gcd_ll(a, b);
    long long l = a / g * b;
    cout << g << "\n" << l << "\n";
    return 0;
}

五、课堂小结与提问

🌟 今日成就

  • 认识了 整除、约数、倍数，知道了 “a | b” 就是 “b 能被 a 整整齐齐地分开”。
  • 学会了用 枚举到 √n 的方式来找约数，大大减少了循环次数。
  • 学会识别 质数与合数，掌握了用 埃拉托斯特尼筛 来快速找出很多质数。
  • 掌握了 最大公约数 gcd 和 最小公倍数 lcm，能用欧几里得算法快速求 gcd。
  • 见识了进阶技巧：用“贡献法”解决倍数统计问题。

这些内容几乎把整数理论里最常见、最实用的武器都发给你了，你已经离 CSP-J 大神又近了一大步！✨

🚧 容易掉坑的地方

  • 把 1 当成质数，或者忘记从 2 开始枚举。
  • 枚举约数时没有考虑 k * k == n 的特殊情况，导致重复计数。
  • int 不够用的时候忘记换成 long long，乘法溢出。

🤔 思考题

如果数据变得非常大，比如 n 可以到 10^12，上面的求约数方法、质数筛方法，还能用吗？哪些地方要改？你会怎么做优化？

恭喜你——整数理论这一关，已经可以自信打怪了！接下来就可以在 CSP-J 真题里大显身手啦！💪🔥