tokitsukaze and RPG

NC21189. tokitsukaze and RPG

描述

tokitsukaze最近沉迷一款RPG。
这个RPG一天有k分钟，每一天从第1分钟开始。
有n种怪物，第i种怪物每天第一次出现的时间为Xi分钟，第二次出现的时间为2*Xi分钟，第三次出现的时间为3*Xi分钟......同一时刻出现的怪物种类越多，打怪获得的经验也越高。
为了高效练级，tokitsukaze想知道在一天内出现怪物种类最多的时间点会出现多少种怪物，这样的时间点有多少个。

输入描述

第一行包括2个正整数n，k(1≤n≤10^5，1≤k≤10^6)，表示有n种怪物，一天有k分钟。
接下来一行包括n个正整数X(1≤Xi≤10^6)，含义如题面所示。

输出描述

输出一行，包括两个整数a，b。
a表示怪物种类数，b表示时间点的个数。

示例1

输入:

3 6
2 2 3

输出:

3 1

说明:

在第6分钟时，3种怪物都出现了。

示例2

输入:

3 5
2 2 3

输出:

2 2

说明:

在第2分钟和第4分钟时，第一种和第二种怪物出现了。

示例3

输入:

6 10
1 2 3 4 5 6

输出:

4 1

说明:

在第6分钟时，出现了第一种、第二种、第三种、第六种怪物。

示例4

输入:

3 5
6 6 6

输出:

0 5

说明:

在第1分钟、第2分钟、第3分钟、第4分钟、第5分钟，都没有出现怪物。

上次编辑到这里，代码来自缓存点击恢复默认模板

C(clang 3.9) 解法, 执行用时: 82ms, 内存消耗: 8164K, 提交时间: 2018-12-07 22:54:55

#include <stdio.h>
int a[1000005]={0};
int b[1000005]={0};
int main()
{
	int m,n,i,x,c,k,d;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)
	{
		scanf("%d",&x);
		b[x]++;
	}
	for(i=1;i<=1000000;i++)
		if(b[i]>0)
			for(c=i;c<=m;c+=i)
				a[c]+=b[i];
	for(i=1,k=0;i<=m;i++)
		if(a[i]>a[k]) k=i;
	for(i=1,d=0;i<=m;i++)
		if(a[i]==a[k]) d++;
	printf("%d %d",a[k],d);

	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 100ms, 内存消耗: 4320K, 提交时间: 2018-12-07 19:06:52

#include<cstdio>
using namespace std;
int n,k,ans,v[1000007],s,tmp;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	scanf("%d",&s),v[s]++;
	for(int i=k;i>=1;i--)
	for(int j=i*2;j<=k;j+=i)
	v[j]+=v[i];
	for(int i=1;i<=k;i++)
	if(ans<v[i])ans=v[i],tmp=1;
	else if(ans==v[i])tmp++;
	printf("%d %d\n",ans,tmp);
}