🔢 容斥原理与综合练习

Inclusion-Exclusion Principle and Practice

容斥原理是整除问题的进阶应用，解决"同时满足多个整除条件"的计数问题。本页还包含整除与余数的综合练习。

📖 3 章节 💡 3 道例题 ✏️ 6 道练习 🎯 难度：进阶 ⏱ 约20分钟

容斥原理 Inclusion-Exclusion Principle

中等必考

在统计"能被A整除或能被B整除"的数的个数时，直接相加会重复计算"同时能被A和B整除"的数。

When counting numbers divisible by A or B, simply adding them together double-counts numbers divisible by both A and B.

📝 两集合容斥公式 / Two-Set Inclusion-Exclusion

|A ∪ B| = |A| + |B| − |A ∩ B|

既能被A整除又能被B整除的数，就是能被 lcm(A,B) 整除的数

Numbers divisible by both A and B are divisible by lcm(A, B)

典型应用：求1到N中能被a或b整除的整数个数

Typical application: Count integers from 1 to N divisible by a or b

能被 a 整除的个数：⌊N/a⌋ ⌊N/a⌋ (floor function)
能被 b 整除的个数：⌊N/b⌋
同时能被 a 和 b 整除的个数：⌊N/lcm(a,b)⌋
答案：⌊N/a⌋ + ⌊N/b⌋ − ⌊N/lcm(a,b)⌋

💡 邓老师提示：⌊x⌋ 表示取整函数（向下取整），即不超过 x 的最大整数。比如 ⌊100/7⌋ = ⌊14.28...⌋ = 14。 ⌊x⌋ is the floor function — the greatest integer ≤ x. E.g., ⌊100/7⌋ = 14.

📌 例题 1 两集合容斥

从 1 到 100 中，是 3 的倍数或 5 的倍数的整数有多少个？How many integers from 1 to 100 are multiples of 3 or 5?

解题思路：容斥原理

3 的倍数：⌊100/3⌋ = 33 个
5 的倍数：⌊100/5⌋ = 20 个
15 的倍数（同时被3和5整除）：⌊100/15⌋ = 6 个
由容斥原理：33 + 20 − 6 = 47 个 Multiples of 3: 33. Multiples of 5: 20. Multiples of 15: 6. By inclusion-exclusion: 33 + 20 − 6 = 47.

📌 例题 2 排除计数

从 1 到 500 中，能被 6 整除但不能被 8 整除的整数有多少个？How many integers from 1 to 500 are divisible by 6 but NOT by 8?

解题思路：总数减去不满足的

6 的倍数：⌊500/6⌋ = 83 个
lcm(6,8) = 24，24 的倍数：⌊500/24⌋ = 20 个
能被6整除但不能被8整除 = 83 − 20 = 63 个 Multiples of 6: ⌊500/6⌋=83. Multiples of lcm(6,8)=24: ⌊500/24⌋=20. Answer: 83−20=63.

综合应用 Comprehensive Applications

进阶真题

整除与余数的综合题通常需要多个知识点联合使用：先利用整除判定法则缩小范围，再用容斥原理计数，或者利用周期性求余数。

Comprehensive problems often require combining multiple techniques: divisibility rules to narrow the range, inclusion-exclusion to count, or periodicity for remainders.

💡 邓老师提示：做综合题时，先读题确定"要求什么"，再决定用什么方法。是"计数问题"用容斥，是"求余数"用周期法，是"整除判定"用各位求和法。

📌 例题 3 综合·周期+判定

下列哪个数能被 11 整除？Which of the following numbers is divisible by 11?

解题思路：11 的判定法则

11 的判定：奇数位数字之和与偶数位数字之和的差，必须是 11 的倍数。
A) 1234：(1+3)−(2+4) = −2 ✗
B) 1463：(1+6)−(4+3) = 0 ✓（0 是 11 的倍数）
C) 2468：(2+6)−(4+8) = −4 ✗
D) 1357：(1+5)−(3+7) = −4 ✗ 1463: alternating sum = (1+6)−(4+3) = 0, which is divisible by 11. Answer: B.

巩固练习 Practice Problems

6 题提交即判

第1题 1 到 200 中，4 的倍数有多少个？How many multiples of 4 from 1 to 200?

第2题 3⁵⁰ 除以 5 的余数是多少？What is the remainder of 3⁵⁰ ÷ 5?

第3题从 1 到 60 中，能被 4 或 6 整除的整数有多少个？How many integers from 1 to 60 are divisible by 4 or 6?

第4题一个正整数 N 除以 3 余 2，除以 7 余 3。满足条件的最小正整数 N 是多少？N leaves remainder 2 when divided by 3, and remainder 3 when divided by 7. Smallest N?

第5题五位数 5271B 能被 9 整除，B 的值是多少？If 5271B is divisible by 9, what is B?

第6题从 1 到 100 中，能被 3 整除但不能被 9 整除的整数有多少个？How many integers from 1 to 100 are divisible by 3 but NOT by 9?

⬅ 上一页余数与模运算 / Remainders & Modular Arithmetic 下一知识点 ➡ 因数与倍数 / Factors & Multiples