打卡信奥刷题（3057）用C++实现信奥题 P6786 「SWTR-6」GCD LCM

P6786 「SWTR-6」GCD LCM题目描述小 A 有一个长度为n nn的序列a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_na1​,a2​,⋯,an​。他想从这些数中选出一些数b 1 , b 2 , ⋯ , b k b_1,b_2,\cdots,b_kb1​,b2​,⋯,bk​满足对于所有i ( 1 ≤ i ≤ k ) i\ (1\leq i\leq k)i(1≤i≤k)b i b_ibi​要么是序列b bb中的最大值要么存在一个位置j jj使得b j b i b_jb_ibj​bi​且b i b j gcd ⁡ ( b i , b j ) l c m ( b i , b j ) b_ib_j\gcd(b_i,b_j)\mathrm{lcm}(b_i,b_j)bi​bj​gcd(bi​,bj​)lcm(bi​,bj​)。如果你不知道gcd ⁡ \gcdgcd和l c m \mathrm{lcm}lcm是什么可以点击最底部的「帮助/提示」部分的链接。小 A 想让选出的数之和尽量大。请求出这个最大值。输入格式第一行一个整数n nn表示序列的长度。第二行n nn个整数a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_na1​,a2​,⋯,an​。输出格式输出一行一个整数表示答案。输入输出样例 #1输入 #14 4 3 2 1输出 #15输入输出样例 #2输入 #210 6 7 18 4 17 10 9 1 3 8输出 #219输入输出样例 #3输入 #33 123456789 234567890 123456789输出 #3246913578说明/提示「样例 1 说明」可以选择b { 2 , 3 } b\{2,3\}b{2,3}因为2 3 gcd ⁡ ( 2 , 3 ) l c m ( 2 , 3 ) 23\gcd(2,3)\mathrm{lcm}(2,3)23gcd(2,3)lcm(2,3)。「数据范围与约定」本题采用捆绑测试。Subtask 15 pointsn ≤ 2 n\leq2n≤2Subtask 220 pointsn ≤ 17 n\leq 17n≤17Subtask 315 pointsa i ≤ 2 × 10 3 a_i\leq 2\times 10^3ai​≤2×103Subtask 415 pointsn ≤ 2 × 10 3 n\leq 2\times 10^3n≤2×103Subtask 510 pointsn ≤ 5 × 10 4 n\leq 5\times 10^4n≤5×104Subtask 610 pointsa i ≤ 10 7 a_i\leq 10^7ai​≤107Subtask 725 points无特殊限制。对于100 % 100\%100%的数据1 ≤ n ≤ 3 × 10 5 1\leq n\leq 3\times 10^51≤n≤3×1051 ≤ a i ≤ 10 9 1\leq a_i\leq 10^91≤ai​≤109。「帮助/提示」gcd ⁡ \gcdgcd表示最大公约数l c m \mathrm{lcm}lcm表示最小公倍数。「来源」【LGR-075】洛谷 8 月月赛 II Div.2 SWTR-06 EZEC Round 3。idea solution data by Alex_Wei。C实现#includebits/stdc.husingnamespacestd;#definelllonglongconstintN3e55;mapint,intmp;intn,a[N];ll ans;intmain(){cinn;for(inti1;in;i)cina[i],mp[a[i]];sort(a1,an1);for(inti1;in;i){ll tmpa[i],cnt0;while(mp[tmp]){cnttmp*mp[tmp],mp[tmp]0;if(tmp%20)tmptmp/2*3;elsebreak;}ansmax(ans,cnt);}coutansendl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容