P6539

_zaa_ · 2022-08-17 17:45:38 · 题解

分析

乍一眼一看可能会感觉到复杂，所以简化了之后，就大概是这样：找到一个数，求数列中是它的倍数的数之和乘以这个数的最大值。

还算蛮简单的，暴力都可以过，于是只用枚举这个数，并计算倍数的个数，就行了。

Code

#include<stdio.h>
int n,a,b[2000010],maxx;
long long s;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        b[a]++;//统计每个数出现的次数，以便后面去找倍数的个数
        maxx<a?maxx=a:a;//找到最大值
    }
    for(int i=1;i<=maxx;i++){//只用枚举到最大值，毕竟后面的数没有倍数在数列中了
        long long m=0;
        for(int j=i;j<=maxx;j+=i) m+=b[j];//统计倍数个数
        if(m>1) s<m*i?s=m*i:m;//找到最大值
    }
    printf("%lld",s);
    return 0;
}