有关CSP-J初赛的一些题目解法

Quartz_Blocks · 2024-09-08 15:36:51 · 个人记录

本文使用 \LaTeX 对一些公式进行排版，Markdown 用于制作文章格式。

本文当中的部分内容为AI总结，经过人工审核，大致是最近本人在练习一些模拟题时的一些特殊的、较难的、容易错的知识点。欢迎各为补充。

有关组合

如何计算组合数

组合数，也称为二项式系数，表示为 \binom{n}{k}，是从 n 个不同元素中不考虑顺序地选择 k 个元素的方法数。它的计算公式是：

其中 n! 表示 n 的阶乘，即从 1 乘到 n 的乘积。

例子

计算 \binom{5}{2}：

1. 首先确定 n 和 k 的值：在这里，n=5 和 k=2。
2. 使用公式计算： \binom{5}{2} = \frac{5!}{2!(5-2)!} = \frac{5!}{2!3!}
3. 计算阶乘： 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 2! = 2 \times 1 = 2 3! = 3 \times 2 \times 1 = 6
4. 代入并简化： \binom{5}{2} = \frac{120}{2 \times 6} = \frac{120}{12} = 10

因此，\binom{5}{2} = 10，意味着从 5 个不同的元素中选择2个元素的组合方式有 10 种。

同余

概念：如果两个整数 a 和 b 除以正整数 m 的余数相同，则称 a 与 b 对模 m 同余，记作 a ≡ b\,\, (\bmod \,m)

性质：

反身性：a ≡ a \,\,(\bmod\, m)

对称性：若 a ≡ b\, (\bmod \,m)，则 b ≡ a \,(\bmod \,\,m)

传递性：若 a ≡ b \,(\bmod \,\,m) 且 b ≡ c \,(\bmod \,\,m)，则 a ≡ c\, (\bmod \,\,m)

加减乘运算：同余式两边可以相加、相减、相乘

易错点：同余式两边不能直接相除，除非除数与模数互质

欧拉函数

欧拉函数 φ(n)：表示小于等于 n 的正整数中与 n 互质的数的个数

e.g. \varphi(5) = 4 (1,2,3,4)

若 n 是质数，则 φ(n) = n-1.

若 n = p₁ᵃ¹ × p₂ᵃ² × ... × pₖᵃᵏ，则 φ(n) = n × (1-1/p₁) × (1-1/p₂) × ... × (1-1/pₖ)

欧拉定理：若 a 与 n 互质，则 a^φ(n) ≡ 1 (mod n)

应用：简化大指数模运算，如计算7¹⁰⁰ mod 10 = 7^(φ(10)=4)²⁵ mod 10 = 1²⁵ = 1

简单的 CRT

求解较小的CRT问题

例子：一盒围棋子，4个4个数多3个，6个6个数多5个，15个15个数多14个，棋子在150~200个，棋子共几个?( )。

方法：暴力枚举

枚举最大的值可以得到数列

筛选 \bmod 4 \ne 3 的项，得到