【Noip模拟 20161005】公约数

2024-04-06 09:42:43

问题描述

小ww最近仔细研究了公约数，他想到了以下问题：现有nn个正整数，从中选k(2≤k≤n)k(2≤k≤n) 个，设这kk个数的最大公约数为gg，则这kk个数的价值为k×gk×g。求这个价值的最大值。

小ww 当然知道答案了。现在他想考考你，你能很快回答出来吗？

输入格式

第一行，一个整数nn。

第二行，nn个正整数。

输出格式

一行一个正整数，表示答案。

输入样例

5

4 6 3 8 9

输出样例

数据范围

对于30%数据，n≤100n≤100

对于100%数据，n≤200000n≤200000，输入第二行每个数字不超过2000000

题目分析

这道题很恶心，我进行因式分解一堆，看到题解发现自己的脑子被驴踢了。正解居然是枚举gcd，然后求有多少个项是gcd的倍数。。。

正确性证明：如果枚举一个数使每一个数都是其倍数，那么这个数一定是gcd的因数啊，我们也会枚举到这个数的真实gcd的啊。

#include<bits/stdc++.h>

using namespace std;

#define RE register long long

#define int long long

#define IL inline

#define N 2000001

int n,a[N],maxx,ans;

inline char gc(){

    static char buf[],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;

}template<class T>inline int read(T &x){

    x=;register char c=gc();

    while(c<)c=gc();

    while(c>)x=(x<<)+(x<<)+(c^),c=gc();

}signed main(){

    freopen("gcd.in","r",stdin),freopen("gcd.out","w",stdout);

    read(n);

    if (n==){puts("");return ;}

    for (RE i=,x;i<=n;++i)

        read(x),a[x]++,maxx=max(maxx,x);

    for (RE i=,sum;i<=maxx;++i){

        sum=;

        for(RE j=i;j<=maxx;j+=i)    sum+=a[j];

        if (sum>) ans=max(ans,sum*i);

    }cout<<ans;

    return ;

}

代码分析

我交了5遍，这一题很坑，第一要开long long，extra有limit data。。。第二：gcd至少两个数，我被坑两次了。

码农公寓