关于集合{1,2,…,100}配对最大化GCD总和的求解问询

问题重述 #

我们有集合 ( S = {1,2,\dots,100} )，需要将其分成50个互不重叠的数对 ((x,y))，每个数对的得分是 ( \text{GCD}(x,y) )，目标是最大化所有数对的得分总和。

你的初始思路的问题 #

你一开始尝试将连续数配对（比如(1,2),(3,4),…,(99,100)），每对GCD为1，总得分50。但这个策略非常低效——仅仅一个数对(100,50)的得分就有50，已经和你50对的总得分持平，显然存在大量更优的配对方式。

最优策略分析 #

要最大化总和，核心逻辑是优先选择GCD尽可能大的数对，因为大的GCD能带来更高的单对得分。具体实现思路是：
从大到小考虑每个正整数 ( d )，将 ( d ) 的倍数两两配对（比如 ( d ) 和 ( 2d )、( 3d ) 和 ( 4d ) 等）。这类配对的GCD恰好是 ( d )——因为连续的两个 ( d ) 的倍数是 ( d*(2k-1) ) 和 ( d*2k )，而 ( 2k-1 ) 和 ( 2k ) 是互质的，所以它们的最大公约数就是 ( d )。

对于每个 ( d )，我们能形成 ( \lfloor \frac{50}{d} \rfloor ) 个这样的数对（总共有 ( \lfloor \frac{100}{d} \rfloor ) 个 ( d ) 的倍数，每两个一组），每组贡献 ( d ) 分，因此总得分的计算公式为：
[
\text{总得分} = \sum_{d=1}^{50} d \times \lfloor \frac{50}{d} \rfloor
]

最终得分计算 #

通过逐个计算每个 ( d ) 的贡献并求和，最终得到的最优总得分是 2080。关键验证点：

• 大数值 ( d ) 贡献突出：比如 ( d=50 ) 对应数对(50,100)，贡献50分；( d=49 ) 对应(49,98)，贡献49分；直到 ( d=26 ) 对应(26,52)，贡献26分。
• 中等数值 ( d )：比如 ( d=25 ) 可形成2对(25,50)、(75,100)，贡献25×2=50分；( d=3 ) 可形成16对，贡献3×16=48分。
• 小数值 ( d )：比如 ( d=2 ) 可形成25对，贡献2×25=50分；而 ( d=1 ) 的配对我们完全不需要，因为更大的 ( d ) 已经覆盖了所有数的配对。

结论 #

最优的总得分是2080，远高于你初始思路得到的50分。核心是放弃低GCD的连续数配对，转而优先构建高GCD的数对，通过从大到小利用每个 ( d ) 的倍数配对来最大化总和。

备注：内容来源于stack exchange，提问作者user1270901