我提一个数论上的剪枝吧:
结果中的数需要满足某种光滑性,即素因子都比较小。我们假定选定的数集中一个数有素因子 p,那么数集的倒数和在分子中必须把这个素因子 p 约分掉,也就是说需要有素因子 p 的那几个数通分后求和正好是 p 的倍数,那么至少不小于 p。
容易看出素因子 23 是一个上界,因为 100 以内 23 的倍数只有 23, 46, 69, 92 这四个,它们倒数和是 25/276,分母是 23 几个倍数的最小公倍数,分子大于 23。但 29 就只有 3 个倍数,倒数和的分子不大于 29 了。
于是,需要检查的数都是 23-光滑的,在 100 以内只有 75 个:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 60, 63, 64, 65, 66, 68, 69, 70, 72, 75, 76, 77, 78, 80, 81, 84, 85, 88, 90, 91, 92, 95, 96, 98, 99, 100
比穷尽 99 个大于 1 的数要节省不少。
更进一步,穷尽的结果中,所有的解都是 19-光滑的。——因为 1/23, 1/46, 1/69, 1/92 这几个数怎么组合都不会约分掉因子 23 的,这个其实也可以提前去掉。19-光滑的数就只有 71 个了。
直接搜索,适当剪枝(提前剪去过大过小的和),这里两三秒跑完。
--
修改:milksea FROM 114.249.226.*
FROM 114.249.226.*