@[ForgotMe](/user/154560) 没想到往前加，谢谢
by ACPC @ 2024-09-21 07:45:21
@[Shunpower](/user/399150) 相邻错的吧，你怎么证明不是需要至少 $k>1$ 步相邻才能找到更优？
by sbno333 @ 2024-09-21 08:09:04
我想一下
by Shunpower @ 2024-09-21 08:20:30
@[sbno333](/user/416975) 考虑交换相邻两项后第一项的贡献至少是原本的两项贡献之和，这两项的gcd一定是交换后第一项的因数，以后的决策也一定不劣
by WeiFanbo @ 2024-09-21 12:15:35
@[Shunpower](/user/399150) @[sbno333](/user/416975)
by WeiFanbo @ 2024-09-21 12:16:16
@[WeiFanbo](/user/439831)
交换相邻两项之后第一项的贡献至少是原本两项贡献和这个没有什么道理吧，还是说我没搞懂您的意思
by Shunpower @ 2024-09-21 12:30:38
@[Shunpower](/user/399150) 假设你第一次选的是x，第二次选的是y，那么贡献是x+gcd(x,y)，因为选的是最小的，所以x<y，y最小也是x+gcd(x,y)，交换后第一项(原本第二项)的贡献就是y，这里不考虑当前gcd已经等于全局gcd的情况
by WeiFanbo @ 2024-09-21 17:23:10