一、核心知识点精讲
0. 本讲定位
在CCFNOICCF NOICCFNOI大纲(2025 年修订版)中,入门级「5. 数学与其他」板块明确列出 初等数论(整除、质
数、模运算、素数筛)。它是CSP−JCSP-JCSP−J复赛里性价比最高、最易被低估的一块:代码短、模板固定、练熟几
乎必拿分。
近五年复赛的数论/代数痕迹明显
T1/T2T1/T2T1/T2位置频繁出现数论小综合,谁把整除、质数、模运算这三板斧练熟,谁就能在前两题快速 ACACAC。
本讲目标:默写「试除判素 / 埃氏筛 / 线性筛 / 快速幂 / 欧几里得」五个模板;能用余数规律做分
类讨论;能写区间筛解决大区间素数计数.
1. 整除与约数
定义:设a,ba,ba,b为整数且b!=0b != 0b!=0。若存在整数kkk使a==k∗ba == k*ba==k∗b,则bbb整除aaa,记b∣ab|ab∣a; 叫 aaa的约数,aaa叫bbb的倍数。
基本性质:① 整除有传递性;② 若a∣ba|ba∣b且a∣ca|ca∣c,则a∣(bx+cy)a|(bx+cy)a∣(bx+cy);③ 约数成对出现:若d∣nd|nd∣n则(n/d)∣n(n/d)|n(n/d)∣n
,故找约数只需枚举到 ;④1的约数只有1。
唯一分解定理:n>1n>1n>1可唯一写成n=p1a1∗p2a2......pkakn = p_1^a1*p_2^a2......p_k^akn=p1a 1∗p2a 2......pka k( 为质数)。由此得两个公式:
约数个数: d(n)=(a1+1)∗(a2+1)∗(a3+1)......(ak+1)d(n) = (a_1+1)*(a_2+1)*(a_3+1)......(a_k+1)d(n)=(a1 +1)∗(a2 +1)∗(a3 +1)......(ak +1)
约数和:
训练点:凡是要数约数个数、约数和、判完全平方(所有 偶),第一步都是分解质因数。
2. 最大公约数与最小公倍数
定义: gcd(a,b)gcd(a,b)gcd(a,b)为同时整除a,ba,ba,b的最大正整数;Lcm(a,b)Lcm(a,b)Lcm(a,b)为被a,ba,ba,b同时整除的最小正整数。核心关系:
⚠先除后乘防溢出:绝不写a∗b/gcda*b/gcda∗b/gcd,当a,b约等于109a,b约等于10^9a,b约等于109时a∗ba*ba∗b会溢出;先除以gcdgcdgcd再乘 。
欧几里得算法(辗转相除)
基于gcd(a,b)==gcd(b,amodb)gcd(a,b) == gcd(b,a mod b)gcd(a,b)==gcd(b,amodb)
LCM 模板:
正在更新中>>....正在更新中>>....正在更新中>>....正在更新中>>....正在更新中>>....正在更新中>>....