[2014-11-01 模拟赛] 最大公约数

2014-11-05
竞赛题解 / 模拟
NOIP模拟赛

描述 Description

话说 CD 比较欠扁，他表示在课室的日子没有教主在旁边打他的日子太寂寞了，所以这一晚，他终于来到了电脑室被打。由于 CD 是大家的宠物，于是大家都来打 CD 了。电脑室里有 n 个人，第 i 个人希望打 CD ai 下。但是太多人打 CD，他又会不爽，于是他规定只能有 K 个人打到他，并且为了公平起见，最终 K 个人打他的次数都必须是相同的，CD 规定这个次数就是这 K 个人希望打他的次数的最大公约数。为什么是最大公约数呢？因为他觉得被打的次数是 GCD 的话他才会变成 Glad CD。之前说了，CD 比较欠扁，于是 CD 希望，K 个人打他的次数的和最大。你能告诉他他最后总共会被打多少下么？

输入格式 InputFormat

第一行两个正整数 n，k。
第二行 n 个正整数，表示每个人希望打 CD 多少下。

输出格式 OutputFormat

输出一个正整数表示 CD 会被打多少下。

样例输入 SampleInput

10 6
2480 4733 3721 3682 2978 692 486 2220 2348 2476

样例输出 SampleOutput

12

NOIP 模拟赛

代码 Code

记录每个数出现了几次，枚举最后的答案 gcd，然后暴力枚举所有它的倍数，看出现次数是否大于等于 k 就可以了。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
int a[500005];
int mid;
long long ans;
int main()
{
    freopen("gcd.in","r",stdin);
    freopen("gcd.out","w",stdout);
    memset(a,0,sizeof(a));t=0;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) scanf("%d",&x),a[x]++,t=max(t,x);
    for (i=1;i<=t;i++)
    {
        for (k=0,j=1;i*j<=t;j++) k+=a[i*j];
        if (k>=m) ans=max(ans,(long long)i*m);
    }
    printf("%I64d\n",ans);
    return 0;
}