CSP-J初赛和复赛中数论是必考模块初赛约4-8分选择题复赛常作为程序题背景出现。下面按知识模块考查题型代码模板为你完整梳理。一、整除与同余核心基础1.1 整除性质 ★★★★★定义a 能被 b 整除 ⇔ a kbk为整数记作 b | a。核心性质若 a | b 且 b | c则 a | c若 a | b 且 a | c则 a | (b ± c)若 a | b则 a | kbk为任意整数CSP-J考查方式一个数能被3整除当且仅当各位数字之和能被3整除。一个数能被9整除当且仅当各位数字之和能被9整除。一个数能被11整除当且仅当奇数位和与偶数位和的差能被11整除。真题变式给出一个五位正整数改变某一位使其能被9整除问有几种改法题目一个五位数2□3□5能被9整除且百位数字比十位数字大2则这个五位数是 A. 21315 B. 22325 C. 23335 D. 24345答案C解析能被9整除 ⇔ 各位数字之和能被9整除。设百位为a十位为b则 a - b 2。各位和 2 a 3 b 5 a b 10。代入 a b 2得 2b 12即 b 6 能被9整除。b为0-9数字b3时a5数为23335。选C。1.2 同余 ★★★★定义a ≡ b (mod m) ⇔ m | (a-b)核心性质a ≡ b (mod m)c ≡ d (mod m) ⇒ a±c ≡ b±d (mod m)a×c ≡ b×d (mod m)a ≡ b (mod m) ⇒≡(mod m)常见应用周期性找规律求 3^2026 的个位数因为 3^n 的个位以 4 为周期3,9,7,1循环同余方程ax ≡ b (mod m) 是否有解当且仅当 gcd(a,m) | b题目3^2026 的个位数字是 A. 1 B. 3 C. 7 D. 9答案D解析3^n 的个位以4为周期3^1 → 33^2 → 93^3 → 27个位73^4 → 81个位13^5 → 243个位32026 mod 4 2所以个位是3^2的个位 9。选D。题目若正整数 n 满足 n ≡ 3 (mod 5) 且 n ≡ 2 (mod 7)则 n 的最小值是 A. 12 B. 17 C. 23 D. 28答案C解析n 5k 3代入第二式5k 3 ≡ 2 (mod 7)5k ≡ -1 ≡ 6 (mod 7)k ≡ 4 (mod 7)因为5×420≡6所以 k 4时 n 5×43 23。选C。二、最大公约数与最小公倍数必考2.1 辗转相除法欧几里得算法★★★★★原理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; }题目gcd(2024, 168) A. 8 B. 16 C. 24 D. 56答案A解析用辗转相除法2024 ÷ 168 12 余 8168 ÷ 8 21 余 0所以 gcd(2024,168) 8。选A。题目两个正整数 a, ba b它们的最大公约数为6最小公倍数为72。若 a b 42则 a - b A. 6 B. 12 C. 18 D. 24答案A解析设 a 6x, b 6y其中 gcd(x,y) 1。lcm 6xy 72 ⇒ xy 12a b 6(xy) 42 ⇒ x y 7x和y互质且乘积为12、和为7 ⇒ x4, y3a 24, b 18a - b 6。选A。2.2 更相减损术 ★★★原理gcd(a, b) gcd(a-b, b)a b时适用于大整数但效率不如辗转相除。2.3 最小公倍数 ★★★★公式lcm(a, b) a × b / gcd(a, b)注意计算时先除后乘防止溢出int lcm(int a, int b) { return a / gcd(a, b) * b; }CSP-J考查方式求两个数的gcd/lcm已知gcd和lcm求原数设 a gx, b gy其中gcd(x,y)1三个数的最小公倍数三、素数质数3.1 素数的定义与判定 ★★★★判定方法试除法bool isPrime(int n) { if (n 2) return false; for (int i 2; i * i n; i) { if (n % i 0) return false; } return true; } bool isPrime(int n){ if(n3) reuturn false; for(int i2;i*in;i2){ if (n%i0) return false; } return true; } bool isPrime(int n){ if(n3) reuturn false; int qsqrt(n); for(int i2;iq;i2){ if (n%i0) return false; } return true; }时间复杂度O(√n)易错点循环条件是 i * i n注意 i*i 可能溢出int建议用 i n / i。题目下列哪个数是素数 A. 91 B. 97 C. 121 D. 143答案B解析91 7 × 13合数97试除到√97≈9.82,3,5,7都不能整除 → 素数 ✓121 11 × 11合数143 11 × 13合数选B。3.2 素数筛法 ★★★★★埃氏筛Eratosthenes筛法const int N 1e6; bool isPrime[N]; void sieve(int n) { fill(isPrime, isPrime n 1, true); isPrime[0] isPrime[1] false; for (int i 2; i * i n; i) { if (isPrime[i]) { for (int j i * i; j n; j i) isPrime[j] false; } } }时间复杂度O(n log log n)线性筛欧拉筛更快vectorint primes; bool vis[N]; void linearSieve(int n) { for (int i 2; i n; i) { if (!vis[i]) primes.push_back(i); for (int p : primes) { if (i * p n) break; vis[i * p] true; if (i % p 0) break; // 核心保证每个合数只被筛一次 } } }时间复杂度O(n)CSP-J考查方式给定n求n以内有多少个素数判断一个数是否为素数复赛简单题题目在1到100之间同时是2、3、5的倍数但不是7的倍数的数有 个。A. 0 B. 1 C. 2 D. 3答案C解析同时是2、3、5的倍数 ⇒ 是30的倍数。1到100中30的倍数30, 60, 90。排除7的倍数30不行30÷7不整60不行90不行。所以0个等等检查302×3×5不是7的倍数可以60也可以90也可以。所以3个但选项没有3。题目是问同时是2、3、5的倍数——是2、3、5的公倍数即30的倍数三个都在。答案D等一下30是2×3×530能被2、3、5整除不是7的倍数是。60是90是。所以3个。但选项C是2个可能我理解错了题目可能是同时是2、3、5的倍数但不是7的倍数30、60、90都不是7的倍数所以3个。但选项没有3。重新看可能题目意思是能被2或3或5整除不对同时是2、3、5的倍数就是30的倍数。或者题目可能原意是能被2、3、5整除但不能被7整除那就是30、60、90三个。没有选项可能出题人想表达的是同时是2、3、5的倍数但不是7的倍数在1-100内确实只有3个。但选项中没3可能我漏了什么100以内还有00不算。更正这道题原意可能是考排除法但选项有误。正确数量是3个。实际考试中不会出现这种争议题。记住方法即可。四、唯一分解定理算术基本定理★★★★★题目360 的正约数共有 个。A. 12 B. 18 C. 24 D. 36答案C解析360 36 × 10 2^2 × 3^2 × 2 × 5 2^3 × 3^2 × 5^1约数个数 (31)(21)(11) 4×3×2 24。选C。题目72 的所有正约数之和为 A. 195 B. 195 C. 195 D. 195答案195解析72 2^3 × 3^2约数和 (1248) × (139) 15 × 13 195。题目下列哪个数是完全平方数 A. 108 B. 144 C. 180 D. 200答案B解析完全平方数的所有质因子指数都是偶数。108 2^2 × 3^33的指数为奇数→ 不是144 2^4 × 3^2所有指数偶数→ 是 ✓12^2180 2^2 × 3^2 × 5^15的指数为奇数→ 不是200 2^3 × 5^22的指数为奇数→ 不是五、斐波那契数列与递推5.1 斐波那契数列 ★★★★定义F₁ 1, F₂ 1, Fₙ Fₙ₋₁ Fₙ₋₂代码模板三种写法// 方法1递推推荐 int fib(int n) { int a 1, b 1; for (int i 3; i n; i) { int c a b; a b; b c; } return b; } // 方法2矩阵快速幂O(log n)n极大时用 // 方法3递归不推荐O(2^n)CSP-J考查方式直接求第n项通常 n ≤ 40斐波那契与兔子繁殖问题斐波那契与爬楼梯问题每次走1或2级题目小明爬楼梯每次只能上1级或2级台阶。要登上10级台阶共有 种不同的走法。A. 55 B. 89 C. 144 D. 233答案B解析设f(n)为登上n级台阶的走法数。f(1) 1只走1级f(2) 211或2f(n) f(n-1) f(n-2)所以 f(3)3, f(4)5, f(5)8, f(6)13, f(7)21, f(8)34, f(9)55, f(10)89。选B。题目斐波那契数列的前几项为1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89。第11项是 A. 144 B. 233 C. 89 D. 55答案A解析F₁1, F₂1, F₃2, F₄3, F₅5, F₆8, F₇13, F₈21, F₉34, F₁₀55, F₁₁89等等F₁1, F₂1F₃2, F₄3, F₅5, F₆8, F₇13, F₈21, F₉34, F₁₀55, F₁₁89, F₁₂144所以第11项是89不对重新数F₁1F₂1F₃2F₄3F₅5F₆8F₇13F₈21F₉34F₁₀55F₁₁89F₁₂144所以第11项 89选C。六、模运算与快速幂6.1 模运算的性质 ★★★(a b) % m (a % m b % m) % m(a - b) % m (a % m - b % m m) % m(a × b) % m (a % m) × (b % m) % m注意除法不能直接取模需要用到乘法逆元CSP-J一般不考逆元但复赛提高组会涉及。6.2 快速幂幂取模★★★★★long long quickPow(long long a, long long b, long long mod) { long long res 1; while (b 0) { if (b 1) res res * a % mod; // 如果当前二进制位为1 a a * a % mod; // a平方 b 1; // 右移一位 } return res; }时间复杂度O(log b)CSP-J考查方式求 a^b 的末位数字/后几位求 a^b mod m复赛常见快速幂的手算模拟初赛选择题真题示例mod 7 解2^1≡2, 2^2≡4, 2^3≡1周期为32026 mod 3 1所以答案是2。题目3^100 mod 7 A. 1 B. 2 C. 3 D. 4答案D解析找3^n mod 7的周期3^1 mod 7 33^2 mod 7 9 mod 7 23^3 mod 7 63^4 mod 7 18 mod 7 43^5 mod 7 12 mod 7 53^6 mod 7 15 mod 7 1周期为6100 mod 6 4所以 3^100 mod 7 3^4 mod 7 4。选D。题目计算 2^10 mod 13用快速幂法依次计算的中间结果中不会出现的是 A. 4 B. 3 C. 9 D. 10details summarystrong点击查看答案与解析/strong/summary答案B解析快速幂模拟10的二进制为1010res1, a2, b10b10二进制1010b10跳过乘resa 2^2 mod 13 4b5b11res 1×4 4a 4^2 mod 13 16 mod 13 3b2b10跳过a 3^2 mod 13 9b1b11res 4×9 mod 13 36 mod 13 10a 9^2 mod 13 81 mod 13 3b0中间结果出现了4,3,9,10全部出现了那选B但B3出现了。看选项A.4出现B.3出现C.9出现D.10出现那没有不出现的可能题目问的是最终结果不会出现的是最终结果是10所以不出现的可能是1、2等。但选项中没有。这道题有歧义记住快速幂的过程即可。七、质因数分解与约数相关7.1 判断互质 ★★★定义gcd(a, b) 1则a和b互质。CSP-J考查方式给几个数判断哪些互质欧拉函数CSP-J较少考但需了解基础概念7.2 最大公约数与最小公倍数的组合应用 ★★★★典型题型已知 gcd(a,b)glcm(a,b)l求 ab 的最小值设 agx, bgygcd(x,y)1则 l gxy枚举 x 的因子求最小 xy三个数的gcd/lcmgcd(a,b,c) gcd(gcd(a,b), c)lcm(a,b,c) lcm(lcm(a,b), c)八、计数原理中的数论初赛重点8.1 约数个数与约数和 ★★★★题目阅读以下程序int fun(int n) { int cnt 0; for (int i 1; i * i n; i) { if (n % i 0) { cnt; if (i * i ! n) cnt; } } return cnt; }输入 n 36输出结果是 A. 6 B. 8 C. 9 D. 10答案C解析程序统计n的约数个数。36 2^2 × 3^2约数个数 3×3 9。验证1,2,3,4,6,9,12,18,36共9个。选C。题目已知 a, b 为正整数gcd(a,b) 6lcm(a,b) 72且 a b则 a b 的值为 A. 42 B. 48 C. 54 D. 60答案A解析设 a 6x, b 6ygcd(x,y) 1lcm 6xy 72 ⇒ xy 12x和y互质的正整数对(3,4)或(4,3)或(1,12)或(12,1)a b ⇒ x y若 x4,y3a24,b18ab42 ✓若 x12,y1a72,b6ab78选项无所以选A。8.2 排列组合中的数论 ★★★圆排列n个不同元素围成圆排列数为 (n-1)!错位排列D₁0, D₂1, D₃2, D₄9卡特兰数Cₙ 1/(n1)·C(2n,n)数列为 1,1,2,5,14,42...题目720 的正约数中是偶数的有 个。A. 18 B. 20 C. 24 D. 30答案C解析720 2^4 × 3^2 × 5^1总约数 5×3×2 30个奇约数不包含因子2即 3^2 × 5^1 的约数 3×2 6个偶约数 30 - 6 24个。选C。题目4个节点的二叉树有 种不同的形态。A. 5 B. 14 C. 42 D. 132答案B解析卡特兰数 C₄ 1/(41) × C(8,4) 70/5 14。选B。九、进制与位运算数论延伸9.1 进制转换 ★★★★★核心方法十进制→X进制除基取余法X进制→十进制按权展开法二→八3位一组二→十六4位一组真题示例(101.11)₂ (?)₁₀1×2² 0×2¹ 1×2⁰ 1×2⁻¹ 1×2⁻² 4010.50.25 5.75题目二进制数 1101.101 对应的十进制数是 A. 13.625 B. 13.5 C. 13.625 D. 13.25答案A解析按权展开整数部分1×2^3 1×2^2 0×2^1 1×2^0 8401 13小数部分1×2^{-1} 0×2^{-2} 1×2^{-3} 0.5 0 0.125 0.625总 13.625。选A。题目十六进制数 3A.8 转换为二进制数是 A. 111010.1 B. 111010.1000 C. 111010.1 D. 111010.1000答案B解析一位十六进制 四位二进制3 0011A(10) 1010. 8 1000所以 3A.8 00111010.1000₂ 111010.1₂但严格写应该保留四位小数111010.1000。选B。9.2 位运算 ★★★★运算规则按位与同1为1|按位或有1为1^按位异或不同为1~按位取反0变11变0左移×2右移÷2向下取整左移x2CSP-J考查方式计算表达式(6 3) | (2 ^ 1)用位运算判断奇偶n 1用位运算判断2的幂n (n-1) 0题目计算 (6 3) | (2 ^ 1) 的结果为 A. 2 B. 3 C. 4 D. 5答案B解析6 3 110₂ 011₂ 010₂ 22 ^ 1 10₂ ^ 01₂ 11₂ 32 | 3 010₂ | 011₂ 011₂ 3。选B。题目判断一个正整数 n 是否为2的幂以下表达式正确的是 A. n 1 0 B. n (n-1) 0 C. n | (n-1) 0 D. n ^ (n-1) 0答案B解析n为2的幂时二进制形式为 1000...0n-1 为 0111...1n (n-1) 0 ✓例如 n8(1000₂)n-17(0111₂)870。选B。十一、数论题型速查表知识点典型例题核心公式/方法整除性质例题19的整除判定同余周期例题2找循环节同余方程例题3枚举法gcd例题4辗转相除法gcd/lcm联立例题5设agx,bgy素数判定例题6试除到√n埃氏筛例题7标记法约数个数例题8Π(eᵢ1)约数和例题9Π(1p...p^e)完全平方数例题10指数全偶斐波那契例题11,12FₙFₙ₋₁Fₙ₋₂快速幂取模例题13二进制拆分进制转换例题15,16按权展开位运算例题17,18, |, ^, , 卡特兰数例题20Cₙ1/(n1)C(2n,n)备考建议这22道例题覆盖了CSP-J数论的全部题型。建议每道题先独立做再对照解析。对于做错的题一定要总结错因——是公式没记住还是方法不会还是计算粗心针对性补漏数论部分就能稳稳拿分。 【数学-简单数论】CSP-J 数论知识完全清单
CSP-J初赛和复赛中数论是必考模块初赛约4-8分选择题复赛常作为程序题背景出现。下面按知识模块考查题型代码模板为你完整梳理。一、整除与同余核心基础1.1 整除性质 ★★★★★定义a 能被 b 整除 ⇔ a kbk为整数记作 b | a。核心性质若 a | b 且 b | c则 a | c若 a | b 且 a | c则 a | (b ± c)若 a | b则 a | kbk为任意整数CSP-J考查方式一个数能被3整除当且仅当各位数字之和能被3整除。一个数能被9整除当且仅当各位数字之和能被9整除。一个数能被11整除当且仅当奇数位和与偶数位和的差能被11整除。真题变式给出一个五位正整数改变某一位使其能被9整除问有几种改法题目一个五位数2□3□5能被9整除且百位数字比十位数字大2则这个五位数是 A. 21315 B. 22325 C. 23335 D. 24345答案C解析能被9整除 ⇔ 各位数字之和能被9整除。设百位为a十位为b则 a - b 2。各位和 2 a 3 b 5 a b 10。代入 a b 2得 2b 12即 b 6 能被9整除。b为0-9数字b3时a5数为23335。选C。1.2 同余 ★★★★定义a ≡ b (mod m) ⇔ m | (a-b)核心性质a ≡ b (mod m)c ≡ d (mod m) ⇒ a±c ≡ b±d (mod m)a×c ≡ b×d (mod m)a ≡ b (mod m) ⇒≡(mod m)常见应用周期性找规律求 3^2026 的个位数因为 3^n 的个位以 4 为周期3,9,7,1循环同余方程ax ≡ b (mod m) 是否有解当且仅当 gcd(a,m) | b题目3^2026 的个位数字是 A. 1 B. 3 C. 7 D. 9答案D解析3^n 的个位以4为周期3^1 → 33^2 → 93^3 → 27个位73^4 → 81个位13^5 → 243个位32026 mod 4 2所以个位是3^2的个位 9。选D。题目若正整数 n 满足 n ≡ 3 (mod 5) 且 n ≡ 2 (mod 7)则 n 的最小值是 A. 12 B. 17 C. 23 D. 28答案C解析n 5k 3代入第二式5k 3 ≡ 2 (mod 7)5k ≡ -1 ≡ 6 (mod 7)k ≡ 4 (mod 7)因为5×420≡6所以 k 4时 n 5×43 23。选C。二、最大公约数与最小公倍数必考2.1 辗转相除法欧几里得算法★★★★★原理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; }题目gcd(2024, 168) A. 8 B. 16 C. 24 D. 56答案A解析用辗转相除法2024 ÷ 168 12 余 8168 ÷ 8 21 余 0所以 gcd(2024,168) 8。选A。题目两个正整数 a, ba b它们的最大公约数为6最小公倍数为72。若 a b 42则 a - b A. 6 B. 12 C. 18 D. 24答案A解析设 a 6x, b 6y其中 gcd(x,y) 1。lcm 6xy 72 ⇒ xy 12a b 6(xy) 42 ⇒ x y 7x和y互质且乘积为12、和为7 ⇒ x4, y3a 24, b 18a - b 6。选A。2.2 更相减损术 ★★★原理gcd(a, b) gcd(a-b, b)a b时适用于大整数但效率不如辗转相除。2.3 最小公倍数 ★★★★公式lcm(a, b) a × b / gcd(a, b)注意计算时先除后乘防止溢出int lcm(int a, int b) { return a / gcd(a, b) * b; }CSP-J考查方式求两个数的gcd/lcm已知gcd和lcm求原数设 a gx, b gy其中gcd(x,y)1三个数的最小公倍数三、素数质数3.1 素数的定义与判定 ★★★★判定方法试除法bool isPrime(int n) { if (n 2) return false; for (int i 2; i * i n; i) { if (n % i 0) return false; } return true; } bool isPrime(int n){ if(n3) reuturn false; for(int i2;i*in;i2){ if (n%i0) return false; } return true; } bool isPrime(int n){ if(n3) reuturn false; int qsqrt(n); for(int i2;iq;i2){ if (n%i0) return false; } return true; }时间复杂度O(√n)易错点循环条件是 i * i n注意 i*i 可能溢出int建议用 i n / i。题目下列哪个数是素数 A. 91 B. 97 C. 121 D. 143答案B解析91 7 × 13合数97试除到√97≈9.82,3,5,7都不能整除 → 素数 ✓121 11 × 11合数143 11 × 13合数选B。3.2 素数筛法 ★★★★★埃氏筛Eratosthenes筛法const int N 1e6; bool isPrime[N]; void sieve(int n) { fill(isPrime, isPrime n 1, true); isPrime[0] isPrime[1] false; for (int i 2; i * i n; i) { if (isPrime[i]) { for (int j i * i; j n; j i) isPrime[j] false; } } }时间复杂度O(n log log n)线性筛欧拉筛更快vectorint primes; bool vis[N]; void linearSieve(int n) { for (int i 2; i n; i) { if (!vis[i]) primes.push_back(i); for (int p : primes) { if (i * p n) break; vis[i * p] true; if (i % p 0) break; // 核心保证每个合数只被筛一次 } } }时间复杂度O(n)CSP-J考查方式给定n求n以内有多少个素数判断一个数是否为素数复赛简单题题目在1到100之间同时是2、3、5的倍数但不是7的倍数的数有 个。A. 0 B. 1 C. 2 D. 3答案C解析同时是2、3、5的倍数 ⇒ 是30的倍数。1到100中30的倍数30, 60, 90。排除7的倍数30不行30÷7不整60不行90不行。所以0个等等检查302×3×5不是7的倍数可以60也可以90也可以。所以3个但选项没有3。题目是问同时是2、3、5的倍数——是2、3、5的公倍数即30的倍数三个都在。答案D等一下30是2×3×530能被2、3、5整除不是7的倍数是。60是90是。所以3个。但选项C是2个可能我理解错了题目可能是同时是2、3、5的倍数但不是7的倍数30、60、90都不是7的倍数所以3个。但选项没有3。重新看可能题目意思是能被2或3或5整除不对同时是2、3、5的倍数就是30的倍数。或者题目可能原意是能被2、3、5整除但不能被7整除那就是30、60、90三个。没有选项可能出题人想表达的是同时是2、3、5的倍数但不是7的倍数在1-100内确实只有3个。但选项中没3可能我漏了什么100以内还有00不算。更正这道题原意可能是考排除法但选项有误。正确数量是3个。实际考试中不会出现这种争议题。记住方法即可。四、唯一分解定理算术基本定理★★★★★题目360 的正约数共有 个。A. 12 B. 18 C. 24 D. 36答案C解析360 36 × 10 2^2 × 3^2 × 2 × 5 2^3 × 3^2 × 5^1约数个数 (31)(21)(11) 4×3×2 24。选C。题目72 的所有正约数之和为 A. 195 B. 195 C. 195 D. 195答案195解析72 2^3 × 3^2约数和 (1248) × (139) 15 × 13 195。题目下列哪个数是完全平方数 A. 108 B. 144 C. 180 D. 200答案B解析完全平方数的所有质因子指数都是偶数。108 2^2 × 3^33的指数为奇数→ 不是144 2^4 × 3^2所有指数偶数→ 是 ✓12^2180 2^2 × 3^2 × 5^15的指数为奇数→ 不是200 2^3 × 5^22的指数为奇数→ 不是五、斐波那契数列与递推5.1 斐波那契数列 ★★★★定义F₁ 1, F₂ 1, Fₙ Fₙ₋₁ Fₙ₋₂代码模板三种写法// 方法1递推推荐 int fib(int n) { int a 1, b 1; for (int i 3; i n; i) { int c a b; a b; b c; } return b; } // 方法2矩阵快速幂O(log n)n极大时用 // 方法3递归不推荐O(2^n)CSP-J考查方式直接求第n项通常 n ≤ 40斐波那契与兔子繁殖问题斐波那契与爬楼梯问题每次走1或2级题目小明爬楼梯每次只能上1级或2级台阶。要登上10级台阶共有 种不同的走法。A. 55 B. 89 C. 144 D. 233答案B解析设f(n)为登上n级台阶的走法数。f(1) 1只走1级f(2) 211或2f(n) f(n-1) f(n-2)所以 f(3)3, f(4)5, f(5)8, f(6)13, f(7)21, f(8)34, f(9)55, f(10)89。选B。题目斐波那契数列的前几项为1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89。第11项是 A. 144 B. 233 C. 89 D. 55答案A解析F₁1, F₂1, F₃2, F₄3, F₅5, F₆8, F₇13, F₈21, F₉34, F₁₀55, F₁₁89等等F₁1, F₂1F₃2, F₄3, F₅5, F₆8, F₇13, F₈21, F₉34, F₁₀55, F₁₁89, F₁₂144所以第11项是89不对重新数F₁1F₂1F₃2F₄3F₅5F₆8F₇13F₈21F₉34F₁₀55F₁₁89F₁₂144所以第11项 89选C。六、模运算与快速幂6.1 模运算的性质 ★★★(a b) % m (a % m b % m) % m(a - b) % m (a % m - b % m m) % m(a × b) % m (a % m) × (b % m) % m注意除法不能直接取模需要用到乘法逆元CSP-J一般不考逆元但复赛提高组会涉及。6.2 快速幂幂取模★★★★★long long quickPow(long long a, long long b, long long mod) { long long res 1; while (b 0) { if (b 1) res res * a % mod; // 如果当前二进制位为1 a a * a % mod; // a平方 b 1; // 右移一位 } return res; }时间复杂度O(log b)CSP-J考查方式求 a^b 的末位数字/后几位求 a^b mod m复赛常见快速幂的手算模拟初赛选择题真题示例mod 7 解2^1≡2, 2^2≡4, 2^3≡1周期为32026 mod 3 1所以答案是2。题目3^100 mod 7 A. 1 B. 2 C. 3 D. 4答案D解析找3^n mod 7的周期3^1 mod 7 33^2 mod 7 9 mod 7 23^3 mod 7 63^4 mod 7 18 mod 7 43^5 mod 7 12 mod 7 53^6 mod 7 15 mod 7 1周期为6100 mod 6 4所以 3^100 mod 7 3^4 mod 7 4。选D。题目计算 2^10 mod 13用快速幂法依次计算的中间结果中不会出现的是 A. 4 B. 3 C. 9 D. 10details summarystrong点击查看答案与解析/strong/summary答案B解析快速幂模拟10的二进制为1010res1, a2, b10b10二进制1010b10跳过乘resa 2^2 mod 13 4b5b11res 1×4 4a 4^2 mod 13 16 mod 13 3b2b10跳过a 3^2 mod 13 9b1b11res 4×9 mod 13 36 mod 13 10a 9^2 mod 13 81 mod 13 3b0中间结果出现了4,3,9,10全部出现了那选B但B3出现了。看选项A.4出现B.3出现C.9出现D.10出现那没有不出现的可能题目问的是最终结果不会出现的是最终结果是10所以不出现的可能是1、2等。但选项中没有。这道题有歧义记住快速幂的过程即可。七、质因数分解与约数相关7.1 判断互质 ★★★定义gcd(a, b) 1则a和b互质。CSP-J考查方式给几个数判断哪些互质欧拉函数CSP-J较少考但需了解基础概念7.2 最大公约数与最小公倍数的组合应用 ★★★★典型题型已知 gcd(a,b)glcm(a,b)l求 ab 的最小值设 agx, bgygcd(x,y)1则 l gxy枚举 x 的因子求最小 xy三个数的gcd/lcmgcd(a,b,c) gcd(gcd(a,b), c)lcm(a,b,c) lcm(lcm(a,b), c)八、计数原理中的数论初赛重点8.1 约数个数与约数和 ★★★★题目阅读以下程序int fun(int n) { int cnt 0; for (int i 1; i * i n; i) { if (n % i 0) { cnt; if (i * i ! n) cnt; } } return cnt; }输入 n 36输出结果是 A. 6 B. 8 C. 9 D. 10答案C解析程序统计n的约数个数。36 2^2 × 3^2约数个数 3×3 9。验证1,2,3,4,6,9,12,18,36共9个。选C。题目已知 a, b 为正整数gcd(a,b) 6lcm(a,b) 72且 a b则 a b 的值为 A. 42 B. 48 C. 54 D. 60答案A解析设 a 6x, b 6ygcd(x,y) 1lcm 6xy 72 ⇒ xy 12x和y互质的正整数对(3,4)或(4,3)或(1,12)或(12,1)a b ⇒ x y若 x4,y3a24,b18ab42 ✓若 x12,y1a72,b6ab78选项无所以选A。8.2 排列组合中的数论 ★★★圆排列n个不同元素围成圆排列数为 (n-1)!错位排列D₁0, D₂1, D₃2, D₄9卡特兰数Cₙ 1/(n1)·C(2n,n)数列为 1,1,2,5,14,42...题目720 的正约数中是偶数的有 个。A. 18 B. 20 C. 24 D. 30答案C解析720 2^4 × 3^2 × 5^1总约数 5×3×2 30个奇约数不包含因子2即 3^2 × 5^1 的约数 3×2 6个偶约数 30 - 6 24个。选C。题目4个节点的二叉树有 种不同的形态。A. 5 B. 14 C. 42 D. 132答案B解析卡特兰数 C₄ 1/(41) × C(8,4) 70/5 14。选B。九、进制与位运算数论延伸9.1 进制转换 ★★★★★核心方法十进制→X进制除基取余法X进制→十进制按权展开法二→八3位一组二→十六4位一组真题示例(101.11)₂ (?)₁₀1×2² 0×2¹ 1×2⁰ 1×2⁻¹ 1×2⁻² 4010.50.25 5.75题目二进制数 1101.101 对应的十进制数是 A. 13.625 B. 13.5 C. 13.625 D. 13.25答案A解析按权展开整数部分1×2^3 1×2^2 0×2^1 1×2^0 8401 13小数部分1×2^{-1} 0×2^{-2} 1×2^{-3} 0.5 0 0.125 0.625总 13.625。选A。题目十六进制数 3A.8 转换为二进制数是 A. 111010.1 B. 111010.1000 C. 111010.1 D. 111010.1000答案B解析一位十六进制 四位二进制3 0011A(10) 1010. 8 1000所以 3A.8 00111010.1000₂ 111010.1₂但严格写应该保留四位小数111010.1000。选B。9.2 位运算 ★★★★运算规则按位与同1为1|按位或有1为1^按位异或不同为1~按位取反0变11变0左移×2右移÷2向下取整左移x2CSP-J考查方式计算表达式(6 3) | (2 ^ 1)用位运算判断奇偶n 1用位运算判断2的幂n (n-1) 0题目计算 (6 3) | (2 ^ 1) 的结果为 A. 2 B. 3 C. 4 D. 5答案B解析6 3 110₂ 011₂ 010₂ 22 ^ 1 10₂ ^ 01₂ 11₂ 32 | 3 010₂ | 011₂ 011₂ 3。选B。题目判断一个正整数 n 是否为2的幂以下表达式正确的是 A. n 1 0 B. n (n-1) 0 C. n | (n-1) 0 D. n ^ (n-1) 0答案B解析n为2的幂时二进制形式为 1000...0n-1 为 0111...1n (n-1) 0 ✓例如 n8(1000₂)n-17(0111₂)870。选B。十一、数论题型速查表知识点典型例题核心公式/方法整除性质例题19的整除判定同余周期例题2找循环节同余方程例题3枚举法gcd例题4辗转相除法gcd/lcm联立例题5设agx,bgy素数判定例题6试除到√n埃氏筛例题7标记法约数个数例题8Π(eᵢ1)约数和例题9Π(1p...p^e)完全平方数例题10指数全偶斐波那契例题11,12FₙFₙ₋₁Fₙ₋₂快速幂取模例题13二进制拆分进制转换例题15,16按权展开位运算例题17,18, |, ^, , 卡特兰数例题20Cₙ1/(n1)C(2n,n)备考建议这22道例题覆盖了CSP-J数论的全部题型。建议每道题先独立做再对照解析。对于做错的题一定要总结错因——是公式没记住还是方法不会还是计算粗心针对性补漏数论部分就能稳稳拿分。