学步园

问题描述

话说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 
3 1

1 2 3

gcd.out

3

数据说明

对于30%的数据，保证k≤n≤20。
对于50%的数据，保证输入中所有数小于5000。

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

题解

一道怪怪的题。

暴力可以枚举答案，看看每个可能的答案能整除多少个数。O(n√n)，80分。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,a[500002],maxs,ct[500002];
void init()
{
	scanf("%d%d",&n,&m);
	int i;
	for(i=1;i<=n;i++) {scanf("%d",&a[i]); maxs=max(maxs,a[i]);}
}
int gcd(int x,int y)
{
	if(y==0) return x;
	else return gcd(y,x%y);
}
void work()
{
	if(m==1) {printf("%d\n",maxs); return ;}
	else if(m==n)
	   {int i,ans=a[1];
	    for(i=2;i<=n;i++) ans=gcd(ans,a[i]);
	    printf("%d\n",ans);
	   }
	int i,j;
	for(i=1;i<=n;i++)
	   {for(j=1;j<=sqrt(a[i]);j++)
	       {if(a[i]%j==0) {ct[j]++; ct[a[i]/j]++;}}
	   }
	for(i=maxs;i>=1;i--)
	   {if(ct[i]>=m) {printf("%d\n",i*m); return ;}}
}
int main()
{
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	init(); work(); 
	return 0;
}

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

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int n,m,a[500002],maxs,ct[500002];
int f[500002];
void init()
{
	scanf("%d%d",&n,&m);
	int i;
	for(i=1;i<=n;i++)
	   {scanf("%d",&a[i]);
	    ct[a[i]]++; maxs=max(maxs,a[i]);
	   }
}
void work()
{
	int i,j;
	for(i=1;i<=maxs;i++)
	for(j=1;j*i<=maxs;j++)
	   f[i]+=ct[j*i];
	for(i=maxs;i>=1;i--)
	   {if(f[i]>=m)
	       {printf("%I64d",(ll)i*m); return;}
	   }
}
int main()
{
	freopen("gcd.in","r",stdin);
	freopen("gcd.out","w",stdout);
	init(); work(); 
	return 0;
}