小红与gcd和sum
时间限制：1秒 空间限制：1024M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！ 
题目描述
小红很喜欢
g
c
d
gcd
gcd 和
s
u
m
sum
sum 。 小红定义一个长度为
k
k
k 的数组
{
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
n
n 的数组
{
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_k
a1,a2,…,ak 的最大公约数，指所有整数共有约数中最大的一个。例如，
12
12
12 、
18
18
18 和
30
30
30 的公约数有
1
,
2
,
3
,
6
1,2,3,6
1,2,3,6 ，其中最大的约数是
6
6
6 ，因此
g
c
d
(
12
,
18
,
30
)
=
6
gcd(12,18,30)=6
gcd(12,18,30)=6 。 非空子序列：从原序列中删除任意个（可以为零，但必须保留至少一个）元素后，保持剩余元素相对顺序不变得到的新序列。
输入描述：
第一行输入一个整数
n
(
1
≦
n
≦
10
5
)
n(1≦n≦10^5)
n(1≦n≦105) ，代表数组的长度。 第二行输入
n
n
n 个整数
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
7
7 种不同的子序列选择方案：
-
{
2
}
\\{2\\}
{2} ，权值为2
×
2
=
4
2×2=4
2×2=4 ； -
{
6
}
\\{6\\}
{6} ，权值为6
×
6
=
36
6×6=36
6×6=36 ； -
{
4
}
\\{4\\}
{4} ，权值为4
×
4
=
16
4×4=16
4×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=16
gcd(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=12
gcd(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=20
gcd(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=24
gcd(2,6,4)×(2+6+4)=2×12=24 。 综上，权值最大的子序列是{
6
}
\\{6\\}
{6} ，权值为36
36
36 。
示例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(maxalogmaxa)，完美适配
n
≤
10
5
n≤10^5
n≤105的大数据约束，简洁高效。
总结
核心逻辑：枚举所有可能的gcd值，计算其倍数元素的总和，取gcd×总和的最大值。 关键操作：统计元素和、枚举公约数、累加对应倍数的元素总和。 效率保障：调和级数复杂度，无需遍历子序列，轻松处理十万级数据。
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=998244353;
void solved()
{
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;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
ll t=1;
//cin>>t;
while(t—) solved();
return 0;
}
