「问题描述」

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

「输入格式」

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

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

「输出格式」

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

「样例输入输出」

「数据说明」

对于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“调和级数求和”。