注意到对于 而言，有这样的性质：若 ，则 。因此可以证明存在最优策略使得有一组内只有一个值相同的数。
还可以发现护结论：这个数在所有数字中要么是值最大的元素，要么是值第二大的元素。证明考虑反证，记选的数是 ，严格前两大的数分别为 ，则
P15741 [JAG 2024 Summer Camp #2] Max Sum of GCD 题解
发布于 2026-03-11 22:56 106 字 1 min read
AGC047E Product Simulation 题解AGC041C Domino Quality 题解P17781 千早爱音不是罪过 题解P17802 [CXOI2026] 想要变成鹰的鱼 题解P17801 [CXOI2026] 大潘小潘向前 p 题解P17800 [CXOI R7-D] 使一颗心不免哀伤 题解P17798 [CXOI R7-B2] 晴涵梦（Hard Version） 题解P17796 [CXOI R7-A] 追忆岁月 题解P17797 [CXOI R7-B1] 晴涵梦（Easy Version） 题解P3838 [IOI 2017] Toy Train 题解P14238 [CCPC 2024 Shandong I] 三角形 题解P15942 [JOI Final 2026] 赌场 / Casino 题解P13184 [GCJ 2017 Finals] Teleporters 题解P17571 「FAOI-R(-2)」数列计数 2024 题解P17618 [Math+Girl×1] dancing With Myself in the sunset / Wheels Mst 题解CF2262E Paired Bracket Sequences 题解CF2246F Whoname and Unsorted Array 题解CF2248F Matrix Elimination 题解AT_arc227_f [ARC227F] Erase and Raise 题解P15992 [PA 2026] 原题加强 2 / Wersja dla profesjonalistów 2 题解P14490 [集训队互测 2018] 小修和小栋猜数字 题解P15001 摧毁时间线 题解CF955F Heaps 题解AT_arc226_d [ARC226D] Penta-Queue 题解AT_arc086_c [ARC086E] Smuggling Marbles 题解P13708 [NWERC 2023] Isolated Island 题解P9483 [NOI2023] 合并书本 题解CF2245G NPC Challenge 题解CF1354G Find a Gift 题解CF1266F Almost Same Distance 题解CF1976F Remove Bridges 题解CF1633F Perfect Matching 题解CF1303G Sum of Prefix Sums 题解CF1307F Cow and Vacation 题解CF1413F Roads and Ramen 题解CF1957F2 Frequency Mismatch (Hard Version) 题解P10546 [THUPC 2024 决赛] 采矿 题解P11018 Monochrome Tree 题解P11149 [THUWC 2018] 城市规划 题解P12692 BZOJ3784 树上的路径 题解P14828 彻彻崩 题解P15076 [ICPC 2024 Chengdu R] Disrupting Communications 题解P17141 [NOI 2026] 传送 题解P5327 [ZJOI2019] 语言 题解P6018 [Ynoi2010] Fusion tree 题解CF1572D Bridge Club 题解CF1268E Happy Cactus 题解CF1299D Around the World 题解P14383 [JOISC 2017] 港口设施 / Port Facility 题解P14019 [ICPC 2024 Nanjing R] 地铁 题解AT_utpc2023_p Priority Queue 3 题解CF1264E Beautiful League 题解AT_agc036_f [AGC036F] Square Constraints 题解P11613 [PA 2016] 覆盖 / Pokrycia 题解P13153 [GCJ 2018 Finals] Jurisdiction Restrictions 题解P10896 移言丁真：Unavoided linyue 题解P11284 「GFOI Round 2」Strings 题解AT_agc029_f [AGC029F] Construction of a tree 题解AT_agc038_f [AGC038F] Two Permutations 题解AT_agc056_c [AGC056C] 01 Balanced 题解AT_arc158_d [ARC158D] Equation 题解CF1061E Politics 题解CF1146G Zoning Restrictions 题解CF1278F Cards 题解CF1286E Fedya the Potter Strikes Back 题解CF1525F Goblins And Gnomes 题解CF1548C The Three Little Pigs 题解CF1762E Tree Sum 题解CF1765C Card Guessing 题解CF1766F MCF 题解CF1842G Tenzing and Random Operations 题解CF2068K Amusement Park Rides 题解CF708D Incorrect Flow 题解CF843E Maximum Flow 题解P10573 [JRKSJ R8] C0mp0nents 题解P10992 [蓝桥杯 2023 国 Python A] 最长同类子串 题解P11531 [THUPC 2025 初赛] 检查站 题解P13583 [NWRRC 2023] Colorful Village 题解P14170 二分图最大匹配期望 题解P14368 [JOISC 2018] 修行 / Asceticism 题解P4055 [JSOI2009] 游戏 题解P4152 [WC2014] 时空穿梭 题解P5287 [HNOI2019] JOJO 题解P5770 [JSOI2016] 无界单词 题解P6031 CF1278F Cards 加强版 题解P6698 [BalticOI 2020] 病毒 (Day2) 题解P7361 「JZOI-1」拜神 题解P9374 「DROI」Round 2 单图 题解P9523 [JOIST 2022] 复制粘贴 3 / Copy and Paste 3 题解P9682 Electro Master 题解P12468 [Math×Girl] 距离 题解CF1101F Trucks and Cities 题解CF1392G Omkar and Pies 题解CF1442D Sum 题解CF1780E Josuke and Complete Graph 题解CF845F Guards In The Storehouse 题解P10084 [GDKOI2024 提高组] 计算 题解P10085 [GDKOI2024 提高组] 染色 题解P11425 [清华集训 2024] 路南柯 题解P11444 [Code+#6] 祖玛 题解P11458 [USACO24DEC] All Pairs Similarity P 题解P11459 [USACO24DEC] It's Mooin' Time P 题解P11678 [USACO25JAN] Watering the Plants P 题解P12074 [OOI 2025] The arithmetic exercise 题解P12706 蜜蜂构造题 题解P13691 [CEOI 2025] highest 题解P13939 [EC Final 2019] Black and White 题解P14106 [ZJCPC 2017] Yet Another Game of Stones 题解P14198 [ICPC 2024 Hangzhou R] Let's Go! New Adventure 题解P14344 [JOISC 2019] 两道料理 / Two Dishes 题解P14347 [JOISC 2019] 灯 / Lamps 题解P14388 [JOISC 2017] 长途巴士 / Long Distance Coach 题解P15077 [ICPC 2024 Chengdu R] Double 11 题解P15108 白井黑子 题解P15301 [ROI 2012 Day 2] army 汗国军队 题解P16160 [ICPC 2016 NAIPC] Jewel Thief 题解P16329 bloom 题解P3665 [USACO17OPEN] Switch Grass P 题解P5400 [CTS2019] 随机立方体 题解P6965 [NEERC 2016] Binary Code 题解P7843 「C.E.L.U-03」布尔 题解P7985 [USACO21DEC] Paired Up P 题解P9139 [THUPC 2023 初赛] 喵了个喵 II 题解P9225 「PEOI Rd1」寻宝（treasure） 题解P9338 [JOIST 2023] 合唱 / Chorus 题解P9962 [THUPC 2024 初赛] 一棵树 题解P3421 [POI 2005] SKO-Knights 题解P13540 [IOI 2025] 羊驼的坎坷之旅（obstacles） 题解P6794 [SNOI2020] 水池 题解P5101 [JOI 2017 Final] 绳 / Rope 题解P9499 「RiOI-2」change 题解P2145 [JSOI2007] 祖玛 题解CF2245F Familiar? 题解CF1239B The World Is Just a Programming Task (Hard Version) 题解P10803 [CEOI 2024] 文本编辑器 题解CF1312G Autocompletion 题解AT_agc049_d [AGC049D] Convex Sequence 题解AT_abc257_h [ABC257Ex] Dice Sum 2 题解AT_abc270_h [ABC270Ex] add 1 题解AT_arc165_e [ARC165E] Random Isolation 题解CF1025G Company Acquisitions 题解CF1349D Slime and Biscuits 题解CF1392F Omkar and Landslide 题解CF1733E Conveyor 题解CF1819D Misha and Apples 题解CF1823F Random Walk 题解CF1919F2 Wine Factory (Hard Version) 题解CF436E Cardboard Box 题解CF850F Rainbow Balls 题解CF869E The Untended Antiquity 题解P10587 「ALFR Round 2」C 小 Y 的数 题解P11191 「KDOI-10」超级演出 题解P11660 我终将成为你的倒影 题解P12479 [集训队互测 2024] 长野原龙势流星群 题解P12587 「KTSC 2019 R2」外星仙人掌 题解P13552 鱼类考古学 题解P13780 「o.OI R2」愿天堂没有分块 题解P14268 [ROI 2015 Day2] 路灯 题解P14761 [Opoi 2025] CCD 的序列 题解P15672 [ICPC 2024 Jakarta R] Narrower Passageway 题解P17145 [NOI 2026] 彩虹树 题解P2235 [HNOI2002] Kathy函数 题解P2284 [HNOI2003] 密室之门 题解P2305 [NOI2014] 购票 题解P3345 [ZJOI2015] 幻想乡战略游戏 题解P3546 [POI 2012] PRE-Prefixuffix 题解P3706 [SDOI2017] 硬币游戏 题解P3920 [WC2014] 紫荆花之恋 题解P4098 [HEOI2013] ALO 题解P4220 [WC2018] 通道 题解P4292 [WC2010] 重建计划 题解P5278 算术天才⑨与等差数列 题解P5524 [Ynoi2012] NOIP2015 充满了希望 题解P5953 [POI 2018] Różnorodność 题解P7215 [JOISC 2020] 首都 题解P8684 [蓝桥杯 2019 省 B] 灵能传输 题解P9965 [THUPC 2024 初赛] 转化 题解P14606 [NWRRC 2025] Games of Chess 题解P11164 [BalkanOI 2023] Permutations 题解P14211 [ROI 2016 Day2] 快递服务 题解P13618 [ICPC 2024 APC] Bánh Bò 题解CF2242F Summer Vacation 题解CF2242E Product of Closures 题解P17064 [JRKSJ R10 热身赛] Infinite Strife, 题解P10103 [GDKOI2023 提高组] 错排 题解CF1033E Hidden Bipartite Graph 题解P17002 [NWERC 2019] 无用交换机 / Disposable Switches 题解CF493E Vasya and Polynomial 题解P11812 [PA 2015] 精确打击 / Kontrmanifestacja 题解P16942 「LAOI-18」铃喵 题解P11815 [PA 2019 Final] 领地 / Terytoria 题解CF1450E Capitalism 题解CF1654F Minimal String Xoration 题解P1001 A+B Problem 题解P14510 夜里亦始终想念着你 miss 题解P16910 「MierOI R2」靈 题解P15419 「yrOI R1」冬日永恒 题解CF1884E Hard Design 题解P15421 像你这样的朋友 题解P16637 春季限定独立集问题 题解P15479 [CERC2012] Non-boring sequences 题解CF1107F Vasya and Endless Credits 题解CF1260F Colored Tree 题解CF1129C Morse Code 题解P5904 [POI 2014] HOT-Hotels 加强版 题解P12866 [JOI Open 2025] 抽奖 / Lottery 题解P12441 [NERC2023] Joy of Pokémon Observation 题解CF1418F Equal Product 题解P16362 [BalticOI 2026] Sort 题解P16433 [APIO 2026 中国赛区] 上升 题解CF1325F Ehab's Last Theorem 题解P12293 [蓝桥杯 2024 国 Java A] 合并小球 题解P11288 [COTS 2017] 模板 Z1 题解P12936 [NERC 2019] Cactus Revenge 题解P16357 [BalticOI 2026] Blocks 题解P13233 [GCJ 2015 Finals] Costly Binary Search 题解AT_arc136_d [ARC136D] Without Carry 题解CF1508E Tree Calendar 题解P9850 [ICPC 2021 Nanjing R] Ancient Magic Circle in Teyvat 题解P6766 [APIO2020] 有趣的旅途 题解CF1444C Team-Building 题解P6009 [USACO20JAN] Non-Decreasing Subsequences P 题解AT_arc122_d [ARC122D] XOR Game 题解AT_abc450_g [ABC450G] Random Subtraction 题解P15502 [ICPC 2025 APC] Book Sorting 题解P15555 [CCPC 2025 哈尔滨站] 比赛 题解CF850D Tournament Construction 题解CF1404D Game of Pairs 题解CF1545C AquaMoon and Permutations 题解CF1830D Mex Tree 题解CF1379E Inverse Genealogy 题解CF1612G Max Sum Array 题解CF1613F Tree Coloring 题解CF1620F Bipartite Array 题解CF1622F Quadratic Set 题解AT_arc127_e [ARC127E] Priority Queue 题解CF1632E2 Distance Tree (hard version) 题解CF1582G Kuzya and Homework 题解CF1623E Middle Duplication 题解CF1679F Formalism for Formalism 题解CF1626F A Random Code Problem 题解CF1734F Zeros and Ones 题解P15653 [省选联考 2026] 星图 题解AT_agc071_c [AGC071C] Orientable as Desired 题解CF1097G Vladislav and a Great Legend 题解CF1579G Minimal Coverage 题解CF1598F RBS 题解CF1614D1 Divan and Kostomuksha (hard version) / CF1614D2 Divan and Kostomuksha (hard version) 题解CF1768E Partial Sorting 题解CF2204G Grid Path 题解CF521D Shop 题解CF852A Digits 题解P15741 [JAG 2024 Summer Camp #2] Max Sum of GCD 题解P15761 [JAG 2025 Summer Camp #1] Colored Tree and Path 题解P3644 [APIO2015] 巴邻旁之桥 题解CF1656F Parametric MST 题解CF1906C Cursed Game 题解CF331D3 Escaping on Beaveractor 题解CF1975G Zimpha Fan Club 题解CF641F Little Artem and 2-SAT 题解CF1344F Piet's Palette 题解CF1381D The Majestic Brown Tree Snake 题解CF1411F The Thorny Path 题解CF1408H Rainbow Triples 题解P15416 「yrOI R1」夏日已逝 题解P15265 [USACO26JAN2] Dynamic Instability P 题解AT_awc0001_a バクテリアの増殖実験 题解P15235 「CROI · R3」浣熊的小游戏 题解P10741 [SEERC 2020] Fence Job 题解AT_ajo2024_final_c Final Exam 题解P9535 [YsOI2023] 连通图计数 题解P15191 [SWERC 2019] Pseudo-Random Number Generator 题解SP27098 FN16OIL - Oil 题解P1691 [ICPC 2016 WF] Oil 题解CF1776I Spinach Pizza 题解P15164 [SWERC 2022] Spinach Pizza 题解CF1730D Prefixes and Suffixes 题解CF1693D Decinc Dividing 题解CF1144G Two Merged Sequences 题解CF1600F Party Organization 题解CF1929E Sasha and the Happy Tree Cutting 题解P5172 [清华集训 2014] Sum 题解P12417 基础构造练习题 1 题解CF1691F K-Set Tree 题解CF2048G Kevin and Matrices 题解P10871 [COTS 2022] 皇后 Kraljice 题解P14610 [NWRRC 2025] Keys and Grates 题解P14564 圆环 题解P14421 [JOISC 2014] 拉面比较 / Ramen 题解P14300 [JOI2023 预选赛 R2] 货物列车 / Freight Train 题解P14415 [JOISC 2015] 遗产继承 / Inheritance 题解P7974 [KSN2021] Delivering Balls 题解P10665 [AMPPZ2013] Bytehattan 题解P9920 「RiOI-3」变换，反演 题解P10045 [CCPC 2023 北京市赛] 线段树 题解P6012 [P5087] 数学 加强版 题解CF2085F2 Serval and Colorful Array (Hard Version) 题解P10756 [COI 2023] Sličnost 题解P3641 [APIO2016] 最大差分 题解P6790 [SNOI2020] 生成树 题解P10832 [COTS 2023] 传 Mapa 题解P14449 [ICPC 2025 Xi'an R] Catch the Monster 题解P14315 [Aboi Round 2] Faputa 题解P5667 拉格朗日插值2 题解CF2163D1 Diadrash (Easy Version) 题解CF2163D2 Diadrash (Hard Version) 题解CF622F The Sum of the k-th Powers 题解P11536 [NOISG 2023 Finals] Curtains 题解P11620 [Ynoi Easy Round 2025] TEST_34 题解P14455 [ICPC 2025 Xi'an R] Imagined Holly 题解P1993 小 K 的农场 题解P3430 [POI 2005] DWU-Double-row 题解P5290 [十二省联考 2019] 春节十二响 题解P5395 第二类斯特林数·行 题解P5396 第二类斯特林数·列 题解P5408 第一类斯特林数·行 题解P6130 随机红包 题解P6898 [ICPC 2014 WF] Metal Processing Plant 题解P7624 [AHOI2021初中组] 地铁 题解P7962 [NOIP2021] 方差 题解P8321 『JROI-4』沈阳大街 2 题解P7315 [COCI 2018/2019 #3] Sajam 题解P5621 [DBOI2019] 德丽莎世界第一可爱 题解P14224 [ICPC 2024 Kunming I] 子数组 题解CF720A Closing ceremony 题解P14303 [GCJ 2011 Finals] Runs 加强版 题解P13382 [GCJ 2011 Finals] Runs 题解SP3912 MTREECOL - Color a tree 题解CF946E Largest Beautiful Number 题解AT_agc003_e [AGC003E] Sequential operations on Sequence 题解P5955 [POI 2018] Pionek 题解P10671 BZOJ1278 向量 vector 题解P12766 [POI 2018 R3] 完备数 Complete numbers 题解P10664 BZOJ3328 PYXFIB 题解P14185 回文子串划分计数 题解CF932G Palindrome Partition 题解AT_abc230_g [ABC230G] GCD Permutation 题解CF870E Points, Lines and Ready-made Titles 题解P7561 [JOISC 2021] 道路の建設案 (Road Construction) (Day2) 题解P14162 [ICPC 2022 Nanjing R] 完美匹配 题解P14154 [ICPC 2022 Nanjing R] 索道 题解P14153 [ICPC 2022 Nanjing R] 停停，昨日请不要再重现 题解P14159 [ICPC 2022 Nanjing R] 邪恶铭刻 题解P14156 [ICPC 2022 Nanjing R] 聊天程序 题解P14161 [ICPC 2022 Nanjing R] 完美回文 题解P14158 [ICPC 2022 Nanjing R] 三角形 题解P9849 [ICPC 2021 Nanjing R] Xingqiu's Joke 题解P9847 [ICPC 2021 Nanjing R] Crystalfly 题解CF794E Choosing Carrot 题解P13509 [OOI 2024] Almost Certainly 题解AT_arc116_f [ARC116F] Deque Game 题解AT_agc029_b [AGC029B] Powers of two 题解P4347 [CERC2015] Book Borders 题解CF185D Visit of the Great 题解P9841 [ICPC 2021 Nanjing R] Puzzle in Inazuma 题解CF729F Financiers Game 题解CF403D Beautiful Pairs of Numbers 题解CF2133E I Yearned For The Mines 题解CF1513E Cost Equilibrium 题解CF317B Ants 题解CF1789F Serval and Brain Power 题解P6122 [NEERC 2016] Mole Tunnels 题解CF1458D Flip and Reverse 题解P13536 [IOI 2025] 神话三峰（triples）（Part 1） 题解P13271 [NOI2025] 机器人 题解AT_agc017_e [AGC017E] Jigsaw 题解P5481 [BJOI2015] 糖果 题解P3805 【模板】Manacher 题解P1943 Local Maxima 题解CF830E Perpetual Motion Machine 题解P3412 仓鼠找sugar II 题解P11073 Game King 题解CF1131G Most Dangerous Shark 题解CF2089D Conditional Operators 题解P12055 [THUPC 2025 决赛] 一个 01 串，n 次三目运算符，最后值为 1 题解P3278 [SCOI2013] 多项式的运算 题解P3272 [SCOI2011] 地板 题解P12179 DerrickLo's Game (UBC002B) 题解CF979E Kuro and Topological Parity 题解CF1919D 01 Tree 题解P4484 [BJWC2018] 最长上升子序列 题解AT_arc195_e [ARC195E] Random Tree Distance 题解B4269 [朝阳区小学组 2019] square 题解CF2091G Gleb and Boating 题解P8456 「SWTR-8」地地铁铁 题解P11952 [科大国创杯初中组 2023] 行走 题解CF2081D MST in Modulo Graph 题解CF1045C Hyperspace Highways 题解P6335 [COCI 2007/2008 #1] STAZA 题解AT_joisc2016_i 電報 题解CF2077B Finding OR Sum 题解P3050 [USACO12MAR] Large Banner G 题解P11856 [CSP-J 2022 山东] 吟诗 题解P11854 [CSP-J 2022 山东] 宴会 题解P11855 [CSP-J 2022 山东] 部署 题解CF804E The same permutation 题解CF1420D Rescue Nibel! 题解CF1996G Penacony 题解CF1951E No Palindromes 题解CF1815F OH NO1 (-2-3-4) 题解CF1977E Tensor 题解CF1943C Tree Compass 题解CF837E Vasya's Function 题解AT_arc149_c [ARC149C] Avoid Prime Sum 题解CF629D Babaei and Birthday Cake 题解CF1042F Leaf Sets 题解CF97D Robot in Basement 题解AT_arc193_a [ARC193A] Complement Interval Graph 题解P11604 [PA 2016] 卡牌 / Gra w karty 题解CF812E Sagheer and Apple Tree 题解CF1310D Tourism 题解CF1693C Keshi in Search of AmShZ 题解CF1137B Camp Schedule 题解CF1270E Divide Points 题解CF1029E Tree with Small Distances 题解CF1943B Non-Palindromic Substring 题解CF446D DZY Loves Games 题解CF1592F2 Alice and Recoloring 2 题解CF1839E Decreasing Game 题解CF1732D2 Balance (Hard version) 题解CF1732D1 Balance (Easy version) 题解CF1981D Turtle and Multiplication 题解CF40E Number Table 题解CF51E Pentagon 题解CF732F Tourist Reform 题解CF793C Mice problem 题解CF126D Fibonacci Sums 题解CF1705E Mark and Professor Koro 题解CF425D Sereja and Squares 题解CF300E Empire Strikes Back 题解CF364C Beautiful Set 题解CF898F Restoring the Expression 题解CF908G New Year and Original Order 题解CF460D Little Victor and Set 题解CF895E Eyes Closed 题解CF1967C Fenwick Tree 题解CF607C Marbles 题解CF1411E Poman Numbers 题解CF1623D Robot Cleaner Revisit 题解CF178F3 Representative Sampling 题解CF1605D Treelabeling 题解CF2056D Unique Median 题解CF1983F array-value 题解CF1238E Keyboard Purchase 题解CF1553F Pairwise Modulo 题解CF484B Maximum Value 题解CF1470D Strange Housing 题解CF1498E Two Houses 题解CF1923E Count Paths 题解CF2049E Broken Queries 题解CF147B Smile House 题解CF1712E1 LCM Sum (easy version) 题解CF1646E Power Board 题解AT_tdpc_tree 木 题解AT_tdpc_lexicographical 辞書順 题解CF2036G Library of Magic 题解CF1834D Survey in Class 题解CF1884D Counting Rhyme 题解CF1886D Monocarp and the Set 题解CF1617D1 Too Many Impostors (easy version) 题解CF1780D Bit Guessing Game 题解CF1804D Accommodation 题解CF1796D Maximum Subarray 题解CF2030B Minimise Oneness 题解CF2030D QED's Favorite Permutation 题解CF1731E Graph Cost 题解CF1442C Graph Transpositions 题解CF1165F1 Microtransactions (easy version) 题解CF1165F2 Microtransactions (hard version) 题解CF1481D AB Graph 题解AT_joi2018ho_e 毒蛇の脱走 (Snake Escaping) 题解P7670 [JOI 2018 Final] 毒蛇越狱 / Snake Escaping 题解P7669 [JOI 2018 Final] 月票购买 / Commuter Pass 题解AT_joi2018ho_d 定期券 (Commuter Pass) 题解CF1358E Are You Fired? 题解CF1453E Dog Snacks 题解P11078 「FSLOI Round I」迷雾 题解P2998 [USACO10NOV] Candy S 题解P10895 选择困难症 题解CF1619E MEX and Increments 题解CF888D Almost Identity Permutations 题解CF863E Turn Off The TV 题解
注意到对于 $\gcd$ 而言，有这样的性质：若 $a>b$，则 $\gcd(a,b)\le a-b$。因此可以证明存在最优策略使得有一组内只有一个值相同的数。 还可以发现护结论：这个数在所有数字中要么是值最大的元素，要么是值第二大的元素。证明考虑反证，记选的数是 $x$，严格前两大的数分别为 $r1,r2$，则
喜欢的话，留下你的评论吧～