垃圾出题人们在30分钟内完成了讨论，出题，命题，造数据，跑std的所有环节

 

luv的化学竞赛题

题目背景

luv_letters 在肝化学竞赛题，他的梦想是混个省一，但是遗憾的是他今年的省二莫名消失了。

题目描述

话说societyniu比较欠扁，他嘲讽luv_letters的省二他都能拿，luv_letters当然不服2333.于是打算搞几份卷子来考考他。

luv_letters有n种化竞卷子，第i种卷子有ai道题。但是societyniu写了太多题他又会不爽（其实是怕输了

于是他规定他只能做K份卷子，并且为了公平起见，K份卷子被写的题数都必须是相同的，societyniu规定这个题数就是这K份卷子的题数的最大公约数。

为什么是最大公约数呢？因为他觉得题数是GCD的话他才会变成GG 的clevel donkey。

之前说了，societyniu热爱理科 因此他希望K种卷子的题数和最大。你能告诉他他最后总共会做多少题么？

输入输出格式

输入格式：

第一行两个正整数n，k。 第二行n个正整数，表示每份卷子的题数。

输出格式：

输出一个正整数表示societyniu会做多少题。

 

输入输出样例

输入样例#1： 3 1 1 2 3 输出样例#1： 3

说明

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

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

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

 

 比赛链接：https://www.luogu.org/problemnew/show/T56342

好吧，这是我出的一道巨水的题

很显然：

题目就相当于问n个数里面选出k个的最大公约数最大是多少。

 

对于30%的数据可以直接暴搜一发。（多爽

 

对于50%的数据...我也不知道（笑，你们可以试试各种玄学剪枝优化qwq

 

对于100%的数据，先开500000大的桶存下每个数出现了几次，

然后枚举最后的答案gcd，

然后再暴力枚举所有它的倍数，看出现次数是否大于等于k就可以了。

这样做的复杂度最坏是O(n+n/2+n/3+…+n/n)=O(nlnn)的。

自行百度调和级数求和

 

 

std:

1 #include <bits/stdc++.h> 2 using namespace std; 3 int n, k, x, m, cnt[500010]; 4 inline int qread(){ 5 register int ch=getchar(),x=0; 6 while(!isdigit(ch)) ch=getchar(); 7 while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar(); 8 return x; 9 } //随手敲快读 10 int main(){ 11 scanf("%d%d", &n, &k); 12 while(n--){ 13 x=qread(); 14 cnt[x]++; //开桶存数出现了几次 15 m= m<x?x:m; 16 } 17 for(int i=m,tmp;i;i--){ 18 tmp = 0; 19 for(int j=i;j<=m;j+=i){ //暴力枚举其所有倍数直接看是否大于K 20 tmp += cnt[j]; 21 } 22 if(tmp>=k){ 23 printf("%lld\n",(long long)i*k); 24 return 0; 25 } 26 } 27 }

真的挺水的

也可以百度K-GCD

转载于:https://www.cnblogs.com/luv-letters/p/9901816.html