题目链接在这里：Problem - D1 - Codeforces
我一开始没有想到从右到左这一个个gcd之间的联系，所以弄的很摸不着头脑
gcd有一个性质，就是 gcd(a,b,c) | gcd(a,b) ，也就是说 这个gcd从右往左是一层层包起来的，多的数的gcd一定是少的数的gcd的一个因子。所以我们考虑用线性筛的思路，从小的gcd一步步推到大的gcd，这是类似于一个链，可以通过线性筛的思路连接。
在统计的时候需要注意每一个数只能有其最大的因数来做贡献，这个大因数包含的小因数不做贡献。
感谢lotato提供思路！
1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const LL MAX=5e6+5; 5 LL n,a[MAX],ans[MAX],cnt[MAX],mx; 6 int main(){ 7 freopen ("d1.in","r",stdin); 8 freopen ("d1.out","w",stdout); 9 LL i,j; 10 // cin>>n; 11 scanf("%d",&n);mx=0; 12 for (i=1;i<=n;i++){ 13 scanf("%d",a+i); 14 mx=max(mx,a[i]); 15 } 16 memset(cnt,0,sizeof(cnt)); 17 for (i=1;i<=n;i++){ 18 for (j=1;j*j<a[i];j++) 19 if (a[i]%j==0){ 20 cnt[j]++; 21 cnt[a[i]/j]++; 22 } 23 if (j*j==a[i]) cnt[j]++; 24 } 25 for (i=1;i<=mx;i++) ans[i]=cnt[i]*i; 26 LL an=0; 27 for (i=1;i<=mx;i++){ 28 for (j=i*2;j<=mx;j+=i) 29 ans[j]=max(ans[j],ans[i]-cnt[j]*i+cnt[j]*j); 30 an=max(an,ans[i]); 31 } 32 printf("%lld",an); 33 return 0; 34 }