三路互质拆分
解题思路
本题要求把 n 拆成三个均 ≥2 的正整数，使它们两两互质。询问多、值域大，需要 O(1) 或极小常数的构造，而不是搜索全部拆分。
- 先判无解：三个数至少为 2+2+2=6，但更强的是两两互质。穷举可知无解集合为 n≤9 以及 n=11,13,17。
- 偶数且 n≥10：至多一个偶数。若 nmod6=2，取 2,3,n−5（n−5 为奇数，与 2 互质，且此时必与 3 互质）；若 nmod6=2，改取 3,4,n−7。
- 奇数且 n≥15（已排除 17）：必须三个奇数。从小到大枚举一小批奇数 a,b，令 c=n−a−b，检查两两互质即可，常数极小。
