同一骨架 2012 年陕西预赛 第 3 题 · P010528
固定总量先把可选参数限制到同一个整数的因数中,再结合实数范围,将最优化转成寻找不越界的最大因数。选出因数后还须恢复原对象,核它真正实现定义中的最优量。
最大公约数受互异正整数最小总和约束,还要构造归一后互素的列表;最佳分解受较小因子不超过平方根约束,须证明固定积时因子差确实随小因子递减。
已知十二个互不相同的正整数之和为 ,则这些正整数的最大公约数的最大值是。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
将最大公约数提出,缩放后的互异正整数和给出下界;再用整除性排除最后一个过大的候选并构造取等。
先回想这道题的想法,再试试当前题。
设最大公约数为 ,十二数写成 。,且 是十二个互异正整数,所以
于是 ;二十五不整除二千零一十六,所以 。取 为一至十一及十八,其和为八十四、最大公约数为一。全部乘二十四,原数和为二千零一十六且最大公约数恰为二十四。因此最大值为 。
1至11的和为66,加18为84;18不同于此前各数。缩放列表含一保证缩放后的原数最大公约数恰好为24,而不是仅知被24整除。
互异正数的总和给共同因子的上限;要证明最大公约数恰达候选,应在缩放构造中保证互素。
先用互异性限制缩放后最小总和,再结合整除性和互素构造确定最大公约数的精确上界。
同一骨架 2012 年陕西预赛 第 3 题 · P010528
固定总量先把可选参数限制到同一个整数的因数中,再结合实数范围,将最优化转成寻找不越界的最大因数。选出因数后还须恢复原对象,核它真正实现定义中的最优量。
最大公约数受互异正整数最小总和约束,还要构造归一后互素的列表;最佳分解受较小因子不超过平方根约束,须证明固定积时因子差确实随小因子递减。
已记下,谢谢!