培玉 · 一试
一试训练题
F2填空题数论
从1,2,…,20中选数，要求所选任意两个不同数都不互相整除。最多能选多少个？
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
思路
按最大奇因子分链配合上半区间构造。
解答
每个数唯一写成2^k·q，q为奇数。相同q的数构成整除链，因此10个奇数q对应10条链，每条最多选1个，至多10。取11至20，各数之比小于2，不可能有整除，达到10。 所求为 。
复核
链中有的只含1个数，仍计入10条；构造必须同时验证互不整除。
方法总结
按最大奇因子分链配合上半区间构造。
为什么评为 F2（会透露解法方向）
按最大奇因子分链配合上半区间构造。
已记下，谢谢！