企业官网建设流程全解析

小红与gcd和sum

时间限制：1秒 空间限制：1024M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

小红很喜欢g c d gcdgcd和s u m sumsum。
小红定义一个长度为k kk的数组{ a 1 , a 2 , … , a k } \{a_1,a_2,…,a_k\}{a1​,a2​,…,ak​}的权值为g c d ⁡ ( a 1 , a 2 , … , a k ) × ( a 1 + a 2 + ⋯ + a k ) gcd⁡(a_1,a_2,…,a_k) × (a_1+a_2+⋯+a_k)gcd⁡(a1​,a2​,…,ak​)×(a1​+a2​+⋯+ak​)。
现在小芳给了小红一个长度为n nn的数组{ a 1 , a 2 , … , a n } \{a_1,a_2,…,a_n\}{a1​,a2​,…,an​}，小红可以从中挑选一个子序列带走。请你帮小红求出她能带走的权值最大的非空子序列。

【名词解释】
g c d ⁡ ( a 1 , a 2 , … , a k ) gcd⁡(a_1,a_2,…,a_k)gcd⁡(a1​,a2​,…,ak​)：即求解a 1 , a 2 , … , a k a_1,a_2,…,a_ka1​,a2​,…,ak​的最大公约数，指所有整数共有约数中最大的一个。例如，12 1212、18 1818和30 3030的公约数有1 , 2 , 3 , 6 1,2,3,61,2,3,6，其中最大的约数是6 66，因此g c d ⁡ ( 12 , 18 , 30 ) = 6 gcd⁡(12,18,30)=6gcd⁡(12,18,30)=6。
非空子序列：从原序列中删除任意个（可以为零，但必须保留至少一个）元素后，保持剩余元素相对顺序不变得到的新序列。

输入描述：

第一行输入一个整数n ( 1 ≦ n ≦ 10 5 ) n(1≦n≦10^5)n(1≦n≦105)，代表数组的长度。
第二行输入n nn个整数a 1 , a 2 , … , a n ( 1 ≦ a i ≦ 10 6 ) a_1,a_2,…,a_n(1≦a_i≦10^6)a1​,a2​,…,an​(1≦ai​≦106)，表示数组中的元素。

输出描述：

输出一个整数，代表权值最大子序列的权值。

示例1

输入：

3 2 6 4

输出：

36

说明：

在这个样例中，一共有7 77种不同的子序列选择方案：

• { 2 } \{2\}{2}，权值为2 × 2 = 4 2×2=42×2=4；
• { 6 } \{6\}{6}，权值为6 × 6 = 36 6×6=366×6=36；
• { 4 } \{4\}{4}，权值为4 × 4 = 16 4×4=164×4=16；
• { 2 , 6 } \{2,6\}{2,6}，权值为g c d ⁡ ( 2 , 6 ) × ( 2 + 6 ) = 2 × 8 = 16 gcd⁡(2,6)×(2+6)=2×8=16gcd⁡(2,6)×(2+6)=2×8=16；
• { 2 , 4 } \{2,4\}{2,4}，权值为g c d ⁡ ( 2 , 4 ) × ( 2 + 4 ) = 2 × 6 = 12 gcd⁡(2,4)×(2+4)=2×6=12gcd⁡(2,4)×(2+4)=2×6=12；
• { 6 , 4 } \{6,4\}{6,4}，权值为g c d ⁡ ( 6 , 4 ) × ( 6 + 4 ) = 2 × 10 = 20 gcd⁡(6,4)×(6+4)=2×10=20gcd⁡(6,4)×(6+4)=2×10=20；
• { 2 , 6 , 4 } \{2,6,4\}{2,6,4}，权值为g c d ⁡ ( 2 , 6 , 4 ) × ( 2 + 6 + 4 ) = 2 × 12 = 24 gcd⁡(2,6,4)×(2+6+4)=2×12=24gcd⁡(2,6,4)×(2+6+4)=2×12=24。
  综上，权值最大的子序列是{ 6 } \{6\}{6}，权值为36 3636。

示例2

输入：

6 1 1 4 5 1 4

输出：

32

说明：

在这个样例中，选择{ 4 , 4 } \{4,4\}{4,4}是最优的。

解题思路

本题核心是枚举公约数 + 贡献求和的数论贪心解法，规避了暴力枚举子序列的高复杂度。对于任意子序列，其权值为gcd × 元素总和，我们只需枚举所有可能的公约数d，统计数组中所有d的倍数的元素之和sum，则该d对应的最大权值为d × sum，最终取所有结果的最大值即可。由于元素范围a_i≤1e6，直接枚举1到最大元素值，通过调和级数累加倍数和。算法时间复杂度为O ( m a x a log ⁡ m a x a ) O(max_a \log max_a)O(maxa​logmaxa​)，完美适配n ≤ 10 5 n≤10^5n≤105的大数据约束，简洁高效。

总结

核心逻辑：枚举所有可能的gcd值，计算其倍数元素的总和，取gcd×总和的最大值。
关键操作：统计元素和、枚举公约数、累加对应倍数的元素总和。
效率保障：调和级数复杂度，无需遍历子序列，轻松处理十万级数据。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1;constll INF=1e18;constll M=1e6+10;constll mod=998244353;voidsolved(){ll n;cin>>n;ll ma=0;vector<ll>a(n);for(ll i=0;i<n;i++){cin>>a[i];if(a[i]>ma)ma=a[i];}vector<ll>s(ma+1);for(auto&x:a)s[x]+=x;ll res=0;for(ll i=1;i<=ma;i++){ll t=0;for(ll j=i;j<=ma;j+=i)t+=s[j];res=max(res,t*i);}cout<<res<<endl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t=1;//cin>>t;while(t--)solved();return0;}