细胞分裂题解

2023-09-05 23:08:07

发布于：广东

258阅读

0回复

0点赞

思路

一道数学题。(可以好好欣赏美丽的 $\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;
}

有帮助，赞一个

去预览

0/2000

全部评论 9

一鸣惊人
#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;ii<=n;i++)//用ii<=n免去了计算sqrt(n)的过程
if(n%i0)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(m11)
{
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;
}

6天前来自内蒙古
0
新辰kimi
666

1周前来自上海
0
༺ཌༀ༒可爱的小鹿茸༒ༀད༻！！
666

2026-04-24 来自浙江
0
一只路边的大蠢材
强

2026-04-04 来自浙江
0
不会c++的小女孩 🏆
ok

2026-03-28 来自浙江
0

Jason

#include<bits/stdc++.h>
using namespace std;
int n,m1,m2,ans = 150000;
int i,j;
int s[10001],f[10001];
bool p[30001];
int prime[501][3],size = 0;
int main(void) {
	memset(p,1,sizeof(p));
	memset(f,0,sizeof(f));
	scanf("%d%d%d",&n,&m1,&m2);
	if (m1 == 1) {
		printf("0");
		return 0;
	}
	for (i = 1; i <= n; i++)
		scanf("%d",&s[i]);
	int xx = floor(sqrt(m1));
	for (i = 2; i <= xx; i++) {

		if (p[i]) {
			if (m1 % i == 0) {
				prime[++size][1] = i;
				prime[size][2] = 1;
			}
		}
		int tim = 2;
		while (tim * i <= m1) {
			p[tim * i] = 0;
			tim++;
		}
	}
	for (i = 1; i <= size; i++) {
		int num = prime[i][1];
		while (m1 % (num * prime[i][1]) == 0) {
			num *= prime[i][1];
			prime[i][2]++;
		}
		prime[i][2] *= m2;
	}
	if (size == 0) {
		prime[++size][1] = m1;
		prime[size][2] = m2;
	}
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= size; j++) {
			if (s[i] % prime[j][1] != 0) {
				f[i] = 150000;
				break;
			}
			int tim = 1;
			long long num = prime[j][1];
			while (s[i] % (num * prime[j][1]) == 0) {
				num *= prime[j][1];
				tim++;
			}
			int an = (prime[j][2]-1) / tim + 1;
			if (an > f[i]) f[i] = an;
		}
	}
	for (i = 1; i <= n; i++)
		if (ans > f[i]) ans=f[i];
	if (ans == 150000) printf("-1");
	else printf("%d",ans);
	return 0;
}

2026-03-18 来自浙江

༺ཌༀ༒ད权威罐头老板༺ཌༀད-
额

2026-03-05 来自福建
0
f u c k ccf
不懂

2024-06-25 来自广东
0
f u c k ccf
?

2024-06-25 来自广东
0