【NOIP模拟赛】最大公约数

2014年11月2日1,5610

【问题描述】

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

【输入格式】

第一行两个正整数n,k。

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

【输出格式】

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

【样例输入输出】

gcd.in

gcd.out

3 1

1 2 3

3

【数据说明】

对于30%的数据,保证k≤n≤20

对于50%的数据,保证输入中所有数小于5000

对于100%的数据,保证输入中所有数小于500000,k≤n。

题解

对于每个数求其所有约数,然后枚举答案,若x是超过K个数的约数,则x是一个解

复杂n√n,可以通过大部分数据

官方题解

先开50W个桶存下每个数出现了几次,然后枚举最后的答案gcd,然后再暴力枚举所有它的倍数,看出现次数是否大于等于k就可以了。这样做的复杂度最坏是O(n+n/2+n/3++n/n)=O(nlnn)的,证明自行Google“调和级数求和”。