今天我们来讲一讲一大专题——基础数论！
用一句话来说数论基础就是：“把正整数拆开、揉碎，研究因数与倍数之间最精妙、最纯粹的数字游戏！”
1. 把它想象成“数字王国的乐高积木”的故事
想象一下，正整数的世界是一个巨大的乐高玩具城。
质数/素数就是“基础单体积木”： 比如 2、3、5、7、11。它们是最原始的零件，没办法再把它们拆成更小的积木。
合数就是“拼装模型”： 比如 12。它不是独立存在的，它是由几个基础单体积木拼成的。
在这个王国
里，所有的计算规则都是在围着积木打转：
最大公约数 (GCD)： 两个大城堡之间，共有最大的一套一模一样的积木核心。
最小公倍数 (LCM)： 为能拼出 A、B两个城堡最少应买的基础积木块数。
取模运算 (Modulo)： 当数字太大装不下时，跨过固定的模数 m，就能保证我们在做超大数计算时，数据永远不会在半路上发生爆内存或溢出的惨剧。
2. 数论基础算法的优缺点喵
数论算法在代码竞赛中是出了名的“高冷神仙”，它有着非常极端的性格：
优点： 速度极快！ 只要你推导出了背后的数学定理（同余定理等），代码通常只需要几行，而别人用多重循环要跑几万年（简单说就是时间长）的题，你用数论公式甚至能在 0 毫秒内瞬间秒杀！
缺点： 极其烧大脑CPU且极其考验细节！ 它是典型的“想得出就满分，想不出就零分”。稍微不注意，就会变成一坨毫无逻辑的错误答案喵。
3. 那它们 C++ 代码长什么样？怎么运行数论基础的核心骨架由以下三大黄金法宝构成，上场考试直接当模板默写：
法宝 A：欧几里得算法 求最大公约数 GCD
运行逻辑（辗转相除）： 大数除以小数，拿余数当新的除数，一直除到余数为 0 为止，最后的除数就是答案。
// 核心骨架：一行搞定最大公约数
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
// 附赠：利用 GCD 求最小公倍数 (LCM)
long long lcm(long long a, long long b) {
// 运行安全注意：先除后乘，防止 a * b 直接爆掉 long long！
return a / gcd(a, b) * b;
}
法宝 B：快速幂 大数求幂取模
运行逻辑（二分拆解）： 算 a^{10} 不要老老实实乘 10 次，把它看成 (a^5)^2。只要指数 b 是奇数，就把底数乘到答案里；如果是偶数，底数原地平方，指数直接折半。
long long power(long long a, long long b, long long m) {
long long ans = 1;
a %= m; // 进门先洗数据，防止底数本身比模数还大
while (b > 0) {
if (b & 1) ans = (ans * a) % m;
// 如果当前二进制最后一位是1（奇数），记账
a = (a * a) % m; // 底数成倍爆炸
b >>= 1; // 指数砍掉一半
}
return ans;
}
法宝 C：欧氏筛法 线性筛素数
运行逻辑（精准打击）： 埃氏筛法会把 12 被 2 和 3 重复筛两次。线性筛的核心在于让每个合数只被它最小的质因子筛掉一次，绝不做无用功。
const int MAXN = 1000005;
bool vis[MAXN]; // 账本：true代表合数，false代表清白的质数
vector<int> primes; // 专门按顺序存放所有的质数积木
void linear_sieve(int n) {
vis[0] = vis[1] = true; // 0 和 1 特判干掉
for (int i = 2; i <= n; i++) {
if (!vis[i]) primes.push_back(i); // 发现新质数，入队
// 核心运行逻辑：用当前数 i 去乘上已知的所有小质数
for (int p : primes) {
if (i * p > n) break; // 超出边界，溜了
vis[i * p] = true; // 精准打上合数标记
// 【终极斩断核心】：如果 i 能整除 p，说明 p 是 i 的最小质因子
// 那么接下来的 (i * 下一个更大的质数) 应该由别人去筛，而不是现在！
//立刻退出！
if (i % p == 0) break;
}
}
}