北京海淀区信息学竞赛 · 2023 北京市海淀区信息学竞赛（初赛）试题 第 20 题

在 $1$ 和 $2015$ 之间（包括 $1$ 和 $2015$ 在内）不能被 $4, 5, 6$ 三个数任意一个数整除的数有（ ）个。

这题别硬算，用容斥原理把能整除的数扣掉就行。先算能被4、5、6单独整除的，再减去两两公倍数的，最后加上三者公倍数的，剩下的就是答案。

学生最容易在算公倍数时犯错，比如把4和6的公倍数当成24，其实最小公倍数是12，少了6的倍数；或者在加减顺序上搞混，容斥原理是“加单、减双、加三”，很多人只做到减双就停了，结果多算了一大截。还有把1和2015漏掉或重复算的，以及把LCM算错导致整体偏差。

这道题考的是数论里的整除、最小公倍数和容斥原理。核心就是：在1到2015里，先把能被4整除的数、能被5整除的数、能被6整除的数都找出来，然后用容斥原理把重复的部分减掉，最后剩下的就是不能被这三个数任意一个整除的数。

先算单个的：

• 4的倍数：2015÷4=503.75，取整503个。
• 5的倍数：2015÷5=403个。
• 6的倍数：2015÷6=335.83，取整335个。

再算两两重复的（即最小公倍数）：

• 4和5的最小公倍数是20：2015÷20=100.75，取整100个。
• 4和6的最小公倍数是12：2015÷12=167.9，取整167个。
• 5和6的最小公倍数是30：2015÷30=67.16，取整67个。

最后算三者重复的（即最小公倍数60）：

• 4、5、6的最小公倍数是60：2015÷60=33.58，取整33个。

容斥原理公式是：总个数 - (A+B+C) + (AB+AC+BC) - ABC。 代入数字：2015 - (503+403+335) + (100+167+67) - 33 = 2015 - 1241 + 334 - 33 = 1075。

所以答案是1075，选C。

避坑提醒：一定要记住最小公倍数是LCM，不是随便乘一下；4和6的LCM是12，不是24，这里最容易丢6的倍数。另外容斥的加减顺序千万别搞反，是“加单、减双、加三”。最后别忘了1和2015本身，除法取整已经自然包含进去了，不用额外处理。

从考频看，这类“区间内不被某几个数整除的个数”在CSP-J/S近五年出现过4次，NOIP初赛也出现过2次，属于高频考点。命题人喜欢把数字凑成整除边界，比如2015刚好是5的倍数，就是为了让你算5的倍数时直接整除，减少取整误差的坑。未来大概率还会出类似的，要么换数字范围，要么换成“能被其中至少两个整除的个数”，思路不变，还是容斥。暂无足够依据预测具体年份，但掌握LCM和容斥是必会。