初等数论基础教学

黄昏中的落雁

2026-10-05 22:12:59

发布于：湖南

8阅读

0回复

0点赞

一、核心知识点精讲
0. 本讲定位
在 $CCF NOI$ 大纲（2025 年修订版）中，入门级「5. 数学与其他」板块明确列出初等数论（整除、质
数、模运算、素数筛）。它是 $CSP-J$ 复赛里性价比最高、最易被低估的一块：代码短、模板固定、练熟几
乎必拿分。
近五年复赛的数论/代数痕迹明显

$T1/T2$ 位置频繁出现数论小综合，谁把整除、质数、模运算这三板斧练熟，谁就能在前两题快速 $AC$ 。
本讲目标：默写「试除判素 / 埃氏筛 / 线性筛 / 快速幂 / 欧几里得」五个模板；能用余数规律做分
类讨论；能写区间筛解决大区间素数计数.

1. 整除与约数

定义：设 $a,b$ 为整数且 $b != 0$ 。若存在整数 $k$ 使 $a == k*b$ ，则 $b$ 整除 $a$ ，记 $b|a$ ；叫 $a$ 的约数， $a$ 叫 $b$ 的倍数。
基本性质：① 整除有传递性；② 若 $a|b$ 且 $a|c$ ，则 $a|(bx+cy)$ ；③ 约数成对出现：若 $d|n$ 则 $(n/d)|n$
，故找约数只需枚举到；④1的约数只有1。
唯一分解定理： $n>1$ 可唯一写成 $n = p_1^a1*p_2^a2......p_k^ak$ （为质数）。由此得两个公式：
约数个数： $d(n) = (a_1+1)*(a_2+1)*(a_3+1)......(a_k+1)$
约数和：

训练点：凡是要数约数个数、约数和、判完全平方（所有偶），第一步都是分解质因数。

2. 最大公约数与最小公倍数

定义： $gcd(a,b)$ 为同时整除 $a,b$ 的最大正整数； $Lcm(a,b)$ 为被 $a,b$ 同时整除的最小正整数。核心关系:

⚠先除后乘防溢出：绝不写 $a*b/gcd$ ，当 $a,b约等于10^9$ 时 $a*b$ 会溢出；先除以 $gcd$ 再乘。

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

基于 $gcd(a,b) == gcd(b,a mod b)$

int gcd(int a, int b) {          
// 递归版
return b == 0 ? a : gcd(b, a % b);
}
int gcd(int a, int b) {          
}
：
// 迭代版
while (b) { int t = a % b; a = b; b = t; }
return a;
}

lcm 模板：

long long lcm(long long a, long long b) {
return a / gcd(a, b) * b;    
}
// ★ 先除后乘

正在更新中>>....正在更新中>>....正在更新中>>....正在更新中>>....正在更新中>>....正在更新中>>....

有帮助，赞一个

去预览

0/2000

这里空空如也

1. 整除与约数

训练点：凡是要数约数个数、约数和、判完全平方（所有 偶），第一步都是分解质因数。

2. 最大公约数与最小公倍数

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

lcm 模板：

热门讨论

训练点：凡是要数约数个数、约数和、判完全平方（所有偶），第一步都是分解质因数。