问题 E: 没有人比我更懂数论

问题 E: 没有人比我更懂数论

时间限制: 1 Sec  内存限制: 128 MB
提交: 357  解决: 22
[状态] [讨论版] [提交] [命题人:]
题目描述
小K学长有一个长度为n的序列a1,a2.....,an。
小K学长要从这个序列中选取一些数,使得选出的这些数中的ai,存在一个数aj,满足条件ai+aj+GCD(ai,aj)=LCM(ai,aj)。
现在小K学长想请你帮忙,选出一些满足条件的数,使得这些数的和最大,你能帮助小K学长吗?
输入
第一行一个整数n,表示序列的长度(1 <= n <= 1x10^3)。
第二行n个数字a1,a2,....,an(1 <= ai <= 10^5)。
输出
输出一行,一个整数表示答案。
样例输入 Copy
4
4 3 2 1
样例输出 Copy
5
提示
[样例1说明]:
可以选择{2,3},因为2 + 3 + GCD(2,3) = LCM(2,3)。