这是什么： 三样数论小工具——余数、最大公约数、找质数。都是几行代码的事，但不会就整道题下不了手。
为什么现在补： 这是 NOI
大纲入门级明文要求的（2.1.5-3），而且直接卡住三道真题：CSP-J
2021 T1 分糖果（P7909）整道题就是一个取模结论，CSP-J
2022 T2 解密（P8814）要解一元二次方程且必须提防
sqrt 精度，CSP-J 2023 T3
一元二次方程（P9750）要用 gcd 把分数约到最简。
前置： L01 的 long long
与复杂度预算。
% 到底给你什么#include <bits/stdc++.h>
using namespace std;
int main() {
cout << 17 / 5 << endl; // 3 —— 整除，小数部分直接砍掉
cout << 17 % 5 << endl; // 2 —— 余数
cout << -17 / 5 << endl; // -3 —— 砍向 0，不是砍向负无穷
cout << -17 % 5 << endl; // -2 —— 所以余数会是负的
return 0;
}⚠️ C++ 的 % 对负数会给出负余数。
想要永远落在 [0, n-1] 里，写
((a % n) + n) % n。
两条必须记住的性质：
📝 a % n 的取值范围是 0 ~ n-1（a ≥
0 时），最大值 n-1 在 a 是"n
的倍数减一"时取到。
📝 a / n 相同 ⟺ a 和 b 落在同一个"长度为 n
的段"里。 判断区间 [L, R] 有没有跨过 n
的倍数，只要看 L / n 和 R / n
是否相等——这一行就是分糖果那题的全部。
最大公约数。三行，背下来：
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int main() {
cout << gcd(24, 18) << endl; // 6
cout << gcd(18, 24) << endl; // 6 —— 谁大谁小都不用管，第一轮会自动换过来
cout << gcd(7, 13) << endl; // 1 —— 互质
return 0;
}📝 约分就是"分子分母同时除以它们的 gcd"：
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int main() {
int p = 18, q = 24;
int g = gcd(abs(p), abs(q)); // 先取绝对值，负数的 gcd 没意义
p /= g;
q /= g;
cout << p << "/" << q << endl; // 3/4
return 0;
}⚠️ 求最小公倍数写
a / gcd(a, b) * b，先除再乘。写成
a * b / gcd(a, b) 的话 a * b 可能先溢出。
判断一个数是不是质数，试除到 √n 就够：
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n) {
if (n < 2) return false; // 0 和 1 都不是质数
for (int i = 2; i * i <= n; i++) { // 注意是 i * i <= n
if (n % i == 0) return false;
}
return true;
}
int main() {
cout << isPrime(1) << endl; // 0
cout << isPrime(2) << endl; // 1
cout << isPrime(97) << endl; // 1
cout << isPrime(91) << endl; // 0 （91 = 7 × 13，容易看走眼）
return 0;
}要一次性找出 1~n 所有质数，别一个个判（那是 O(n√n)），用埃氏筛：
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
bool notPrime[N]; // 全局数组自动初始化为 false
int main() {
int n = 30;
notPrime[0] = notPrime[1] = true; // 0 和 1 不是质数
for (int i = 2; i * i <= n; i++) {
if (!notPrime[i]) { // i 是质数
for (int j = i * i; j <= n; j += i) {
notPrime[j] = true; // 把 i 的倍数全划掉
}
}
}
for (int i = 2; i <= n; i++) {
if (!notPrime[i]) cout << i << " ";
}
cout << endl; // 2 3 5 7 11 13 17 19 23 29
return 0;
}📝 内层从 i * i 开始，不是从
2 * i。 比 i×i
小的倍数（2i、3i…）早就被更小的质数划掉了。
⚠️ 坑 1：sqrt 返回
double，大数会给出错误答案。
long long n = 999999999999999999LL;
long long r = sqrt(n); // 结果可能差 1
if (r * r == n) { ... } // 于是判断就错了double 只有约 15~16 位有效数字，long long
能装 18 位以上，转换过程中必然丢精度。
正确姿势是先算再修：
#include <bits/stdc++.h>
using namespace std;
long long mySqrt(long long n) { // 返回 floor(sqrt(n))
if (n < 0) return -1;
long long r = (long long)sqrt((double)n);
while (r > 0 && r * r > n) r--; // 大了就往下修
while ((r + 1) * (r + 1) <= n) r++; // 小了就往上修
return r;
}
int main() {
long long n = 999999999999999999LL;
long long r = mySqrt(n);
cout << r << " " << (r * r == n ? "是完全平方数" : "不是") << endl;
return 0;
}📝 同理，判质数的循环条件写
i * i <= n，不要写
i <= sqrt(n)——既慢（每轮都调一次
sqrt）又不准。
⚠️ 坑 2：1 不是质数，2 是质数。
isPrime 里那句 if (n < 2) return false;
漏掉的话，1 会被判成质数（循环一次都不进，直接
return true）。这个边界每年都有人栽。
📝 2 是唯一的偶质数。 见到"枚举质数"的题，先在纸上把 1、2 这两个边界过一遍。
按难度排，先做第一道：
CSP-J 2021 T1 分糖果（P7909） —— n 个小朋友，你拿 k 颗糖（L ≤ k ≤ R），每轮每人各拿一颗，直到不够分，剩下的归你。求最多能剩几颗。数据范围 2 ≤ n ≤ L ≤ R ≤ 10⁹，所以不能枚举 k。整道题就是 1.1 里那两条📝。
CSP-J 2022 T2 解密（P8814） —— 给 n、e、d，求
p、q 使 n = p×q 且 e×d = (p−1)(q−1)+1。把第二个式子展开，你会发现 p+q
也能直接算出来——于是 p、q 就是某个一元二次方程的两个根。n ≤
10¹⁸，long long 和 sqrt
精度两个坑都在这道题上等着你。
CSP-J 2023 T3 一元二次方程（P9750） —— 输出格式极其啰嗦（分数要约到最简、根号要化简），gcd 是其中一环。这是 T3，属于"行有余力"，前两道做完再碰。
思路提示见 S8_真题分级提示.md，代码自己写。
k 在 [L, R] 之间取值，什么条件下
k % n 能取到最大值 n - 1？gcd(0, 5) 等于多少？i * i <= n 而不是
i <= sqrt(n)？L / n != R / n 时——说明区间跨过了至少一个 n
的倍数，那么"n 的倍数减一"这个数一定落在区间内。否则 L 和 R
在同一段里，k % n 随 k 单调递增，最大值就是
R % n。gcd(0, 5) → gcd(5, 0) → 边界返回
5。sqrt 返回
double，大数会丢精度导致边界判错；而且每轮循环都调一次
sqrt 白白变慢。i * i
是纯整数运算，又快又准。以后学： 线性筛、同余、逆元、扩展欧几里得都属于提高级（大纲 2.2.5），本次冲刺不需要。