易混 2022 年山东预赛 · P006889
两题都涉及平方关系，但可压缩的信息不同。要求平方和被某整数整除时，剩余类能完整判定这条整除关系；要求两个数之和确为完全平方数时，同余只是必要筛选，还须实际构造满足等式的数对。
前题根据禁配类型选出尽可能多的数；后题要迫使两色中出现目标数对，可先构造两色无法避开的三点结构。
培玉 · 一试
2023 年北京预赛
F3填空题组合计数综合
是集合 的子集，满足任意两个元素的平方和不是 的倍数，则 的最大值是。（这里 表示 的元素个数）
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
提示
限制条件只涉及平方和是否被 整除，因此按模 考察平方剩余。
思路
确定唯一被禁止的两元素类型后，先给出基数上界，再构造达到上界的集合。
解答
任意整数的平方模 的余数只能是
其中平方余数为 当且仅当原整数能被 整除。若两个整数中恰有一个能被 整除，则它们的平方和模 的余数为 或 ；若两个整数都不能被 整除，则平方和模 的余数属于
这些余数都不为 。因此，两个不同整数的平方和是 的倍数，当且仅当二者都能 被 整除。
所以 中至多含有一个 的倍数。集合 中 的倍数有
个，不是 的倍数的数有 个，故
取 为所有不被 整除的数，再加入一个 的倍数，例如加入 ，则其中没有 两个不同的 的倍数，条件成立，且 。因此最大值为
复核
逐一计算 的平方余数，确为 ；非零平方余数的任意两项之和 只可能为 ，不会漏掉互补余数。又因 ，非倍数计数为 。上界与显式构造一致，故最大值已经达到。
方法总结
当两两限制只涉及整除性时，先把元素按模数的剩余类压缩，并找出哪些类型之间不能共存。 极值题必须分两步完成：禁配关系给出上界，再选取所有相容类型并补入允许的少量元素， 构造出达到上界的集合。
为什么评为 F3（会透露解法方向）
关键是识别平方和被9整除等价于两数均为3的倍数，再完成至多一个倍数的上界及构造。
联系 · 1 条
已记下，谢谢！