培玉 · 一试
2012 年河南预赛 · 第 1 题
F2填空题组合计数综合
在小于 的正整数中，取出三个不同的数，使它们的和能够被 整除，则不同的取法种数为
。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
思路
按 的余数将候选正整数分为三类：三个数的和能被 整除，当且仅当三个数的余数全相同或三类余数各取一个。
解答
小于 的正整数为 ，共 个数。按除以 的余数分为三类： 余数为 的集合 共 个； 余数为 的集合 共 个； 余数为 的集合 共 个。 三数之和能被 整除，当且仅当三数同属一个余数类，或三类各取一个。因此不同选法总数为
复核
选出的是三个不同数且不计顺序，故同一余数类内取三数用组合数；三类各取一个时三个数自动互异且无序唯一，无需乘 。注意“小于 ”包含 不包含 ，故模 余 的一类有 个数。
方法总结
固定项数的整除组合问题，先按模数余数分类，列尽余数和同余于 的互斥配比，再分别用组合数与分步乘法计数。
为什么评为 F2（会透露解法方向）
余类分组后须列尽三数和为零的模式，并区分同类组合与跨类乘法，避免排列重数。
已记下，谢谢！