整除计数与容斥 · 知识点讲解

本知识点

整除计数容斥原理倍数个数

解题路径

分别计算各类倍数个数
减去重复计数的公倍数
处理补集并检查端点

配套例题

看懂这几道题，就掌握了这个点

先做再看解析；做错的题建议加入练习单，到「诊断练习」里集中攻克。

题 A1-04-011难度 E · 挑战

⑴ 从 $1$ 到 $1000$ 的 $1000$ 个数中，能被 $4$ 或者 $6$ 整除的整数有多少个？

⑵ 在小于 $2021$ 的正整数中，即不能被 $2$ 整除也不能被 $3$ 或 $5$ 整除的数有几个？

查看答案解析

解：⑴ 1～1000中4的倍数有250个，6的倍数有166个，12的倍数有83个。由容斥原理得 $250 ＋ 166 - 83 ＝ 333$ 个。

⑵ 1～2020中，至少能被2、3、5之一整除的数有 $1010 ＋ 673 ＋ 404 - 336 - 202 - 134 ＋ 67 ＝ 1482$ 个。

答：⑴ 333个；⑵ $2020 - 1482 ＝ 538$ 个。

题 A1-04-032

在1、2、3、 $\dots$ 、2020这2020个自然数中有多少个自然数能同时被2和3整除，而不能被5整除？

查看答案解析

[ 2 , 3 ] = 6 ， [ 2 , 3 , 5 ] = 3 0

$2020 \div 6 = 336 \dots \dots 4$ ， $2020 \div 30 = 67 \dots \dots 10$

所以：能同时被2和3整除，而且不能被5整除的数有 $336 - 67 = 269$ （个 $)$

题 A1-04-036

先将100个杯子排成一列，杯口朝上．从左向右从1数到100，数到3的倍数时把杯子翻过来；再从左向右从1数到100，数到7的倍数时把杯子翻过来，那么最后有______个杯子杯口朝上．

查看答案解析

1 0 0 个杯子中，有 3 3 个 3 的倍数， 1 4 个 7 倍数，有 4 个 2 1 的倍数

∴ $100 - 33 - 14 + 4 \times 2 = 61$ 个

题 A1-04-037

先将100个杯子排成一列，杯口朝上．从左向右从1数到100，数到3的倍数时把杯子翻过来；再从右向左从1数到100，数到7的倍数时把杯子翻过来，那么最后有______个杯子杯口朝上．

查看答案解析

解：设杯子从左到右编号为1到100，从左数编号为 $p$ 的杯子，从右数它是第 $101 - p$ 个。第一次翻动要求 $p$ 是3的倍数，第二次翻动要求 $101 - p$ 是7的倍数。

1～100中第一次翻动33个，第二次翻动14个；联立 $p \equiv 0 (mod 3)$ 与 $p \equiv 3 (mod 7)$ ，得 $p ＝ 3 、 24 、 45 、 66 、 87$ ，共5个杯子翻动两次。

答：最后杯口朝上的有 $100 - 33 - 14 ＋ 2 \times 5 ＝ 63$ 个。

题 A1-04-038

我们知道4不是3的倍数，5也不是3的倍数，但4与5的和却是3的倍数．现从1到100这100个自然数中，任意选两个不同的数组成一个有序数对 $(m, n)$ ，其中 $m$ ， $n$ 均不是3的倍数，但 $m$ 与 $n$ 的和恰好是3的倍数，则这样的有序数对共有________对．

查看答案解析

两个数的和是3的倍数，只有一个除3余1的数和一个除3余2的数的和是3的倍数，

所以， $m$ 是除3余1的数， $n$ 必是除3余2的数或 $m$ 是除3余2的数， $n$ 必是除3余1的数，

而从1到100这100个自然数中，除3余1的数有34个，除3余2的数有33个，

满足条件的有序数对共有 $34 \times 33 + 33 \times 34 = 2244$ 对，