细胞分裂 题解
2023-09-05 23:08:07
发布于:广东
60阅读
0回复
0点赞
思路
一道数学题。(可以好好欣赏美丽的公式了)
先来看看题目要做什么:枚举(为这里的秒数),使得保证(即被整除)时,最小。
显然对于这样的数据,我们是存不下的数值的,更不用说对进行一系列的操作和计算了。但是题目中给出的的条件很有意思,结合着我们需要满足的目的,不难看出这个条件是暗示让我们对和进行质因数分解,然后再通过质因数和其指数判断是否能满足。
而这样,我们就成功地将一个乘方的计算,转换成了指数相乘的计算。若则
那么怎么判断是否满足呢,举个栗子:
2 | 3 | 3 | 3 | 4 | 0 | |
1 x | 2 x | 1 x | 1 x | 1 x | 0 x |
只要满足对于的每一个质因数,它的指数都要比来的小即可。在这里,1 x , 取最小的为。我们可以循环每一个的质因数,然后让取能够满足规定指数大小关系的最小值,最后对于每一个打擂台求出最后的最小值。
什么时候永远也不能满足要求呢?那就是当中有没有的质因数的时候。因为无论给乘多少次方,都不可能创造新的质因数。就比如若的质因子指数为1时,就不可能满足要求。
最后,怎么把质因数和它的指数存下来呢,我们注意到题目规定如果开30000大小的数组就造成了浪费,小于30000的质数只有3300左右个,我们可以在初始化时先跑一遍质数存下来,以便后期使用。
对了,还有一个特判,也就是当 时,怎样都可以均分,应该直接输出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;
}
全部评论 2
不懂
2024-06-25 来自 广东
0?
2024-06-25 来自 广东
0
有帮助,赞一个