细胞分裂 题解

思路

一道数学题。(可以好好欣赏美丽的$\bold L\bold A\bold T\bold E\bold X$公式了)
先来看看题目要做什么：枚举$S^n_i$($n$为这里的秒数)，使得保证$m^{m2}_1|S^n_i$(即$S^n_i$被$m^{m2}_1$整除)时，$n$最小。

显然对于$1\leq m_1\leq 30000,1\leq m_2 \leq 10000$这样的数据，我们是存不下$M$的数值的，更不用说对$M$进行一系列的操作和计算了。但是题目中给出的$M=m^{m2}_1$的条件很有意思，结合着我们需要满足$m^{m2}_1|S^n_i$的目的，不难看出这个条件是暗示让我们对$M$和$S_I$进行质因数分解，然后再通过质因数和其指数判断是否能满足$m^{m2}_1|S^n_i$。

而这样，我们就成功地将一个乘方的计算，转换成了指数相乘的计算。$($若$m_1=p^i_1p^j_2...p^k_n,$则$m^{m2}_1=p^{m_2\ i}_1p^{m_2\ j}_2...p^{m_2\ k}_n$$)$
那么怎么判断是否满足$m^{m2}_1|S^n_i$呢，举个栗子：

	$p_1$	$p_2$	$p_3$	$p_4$	$p_5$	$p_6$
$M$	2	3	3	3	4	0
$S^n_1$	1 x $n$	2 x $n$	1 x $n$	1 x $n$	1 x $n$	0 x $n$

只要满足对于$M$的每一个质因数$p$，它的指数都要比$S^n_i$来的小即可。在这里，1 x $n\geq 5$, 取最小的$n$为$5$。我们可以循环每一个$M$的质因数，然后让$n$取能够满足规定指数大小关系的最小值，最后对于每一个$S_i$打擂台求出最后$n$的最小值。

什么时候永远也不能满足要求呢？那就是当$M$中有$S_I$没有的质因数的时候。因为无论给$S_I$乘多少次方，都不可能创造新的质因数。就比如若$M$的质因子$p_6$指数为1时，就不可能满足要求。

最后，怎么把质因数和它的指数存下来呢，我们注意到题目规定$1\leq m_1\leq 30000$如果开30000大小的数组就造成了浪费，小于30000的质数只有3300左右个，我们可以在初始化时先跑一遍质数存下来，以便后期使用。

对了，还有一个特判，也就是当 $m_1=1$时，怎样都可以均分，应该直接输出0否则进入后面由于1不是质数，会输出 -1。

AC代码

#include<bits/stdc++.h>
using namespace std;
int prime[3310],mx[3310],sx[3310],s[10010];//存下质因数，M的指数,Si的指数，还有所有的s
bool isprime(int n)//判断质数
{
	for(int i=2;i*i<=n;i++)//用i*i<=n免去了计算sqrt(n)的过程
		if(n%i==0)return false;
	return true;
}
int main()
{
	int n,m1,m2,tot=0,minn=1<<30,flag=0,np,ff=0;//tot记录质数总数，minn打擂台，flag记录某一个Si是否有结果，ff记录所有Si是否有结果
	prime[++tot]=2;
	for(int i=3;i<=30000;i+=2)//跳着判断，心里觉得会快点，实际上差别不大
		if(isprime(i))
			prime[++tot]=i;
	scanf("%d %d %d",&n,&m1,&m2);
	for(int i=1;i<=n;i++)scanf("%d",&s[i]);
	if(m1==1)
	{
		printf("0");
		return 0;
	}
	for(int i=1;prime[i]<=m1;i++)//对m1进行质因数分解
	{
		while(m1%prime[i]==0)
		{
			m1/=prime[i];
			mx[i]++;
		}
		mx[i]*=m2;//在这里就相当于m1^m2的操作
	}
	for(int i=1;i<=n;i++)
	{
		memset(sx,0,sizeof(sx));//每次清空si的指数的数组备用
		for(int j=1;j<=tot;j++)//对Si进行质因数分解，由于m<30000，只需要判断Si是否有30000以下的质因数就行了
		{	                     //而且我们只存了30000以下的质数，用for循环判断prime[i]<=s[i]会RE
			while(s[i]%prime[j]==0)
			{
				s[i]/=prime[j];
				sx[j]++;
			}
		}
		np=1;//每一次的n
		flag=0;
		for(int j=1;j<=tot;j++)
		{
			if(mx[j]&&sx[j])//如果这个质因数两者都有
			{
				flag=1;
				if(mx[j]>sx[j]*np)np=mx[j]/sx[j];
				if(mx[j]>sx[j]*np)np++;
			}
			else if(mx[j]&&!sx[j]){flag=false;break;}//没有则不可能满足要求，退出循环
		}
		if(flag)minn=min(minn,np),ff=1;//打擂台
	}
	if(ff)printf("%d",minn);
	else printf("-1");
	return 0;
}