记录编号	19043	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]细胞分裂	最终得分	100
用户昵称	Pom	是否通过	通过
代码语言	C++	运行时间	2.041 s
提交时间	2010-09-28 09:21:12	内存使用	0.40 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN=10000;
const int oo=100000000;

int DAT,ans,i,j,k,tot,su[10000],num[10000],M,mi,n;
bool b[30010];
int fans,sum[10000],q;

void init()
{
	freopen("cell.in","r",stdin);
	freopen("cell.out","w",stdout);
	scanf("%d%d%d",&DAT,&M,&mi);
	memset(b,false,sizeof(b));
	q=M;
	for (i=2;i<=30000;i++)
		if (!b[i])
		{
			su[++tot]=i;
			j=i;
			for (;;)
			{
				b[j]=true;
				j=j+i;
				if (j>30000) break;
			}
		}
	for (i=1;i<=tot;i++)
	{
		for (;;)
		{
			if (M%su[i]==0)
			{
				M=M/su[i];
				num[i]++;
			}
			else break;
		}
	}
	for (i=1;i<=tot;i++)
		num[i]*=mi;
	fans=-1;
}

void solve()
{
	scanf("%d",&n);
	memset(sum,0,sizeof(sum));
	for (i=1;i<=tot;i++)
	{
		for (;;)
			if (n%su[i]==0) 
			{
				sum[i]++;
				n=n/su[i];
			}
			else break;
	}
	ans=0;
	if (q==1)
	{
		ans=0;
		return;
	}
	for (i=1;i<=tot;i++)
	{
		if (num[i] && !sum[i]) 
		{
			ans=-1;
			return;
		}
		k=sum[i];
		j=1;
		for (;;)
		{
			if (k>=num[i]) break;
			j=j+1;
			k=k+sum[i];
		}
		if (j>ans) ans=j;
	}
}

int main()
{
	init();
	for (;DAT>0;DAT--)
	{
		solve();
		if (fans==-1) fans=ans;
		else 
			if (ans!=-1)
				fans=min(ans,fans);
	}
	printf("%d\n",fans);
	return 0;
}