题解
2024-12-31 16:29:13
发布于：浙江
#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;
}
全部评论 1
啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧吧啊吧
2024-12-31 来自 浙江
0
有帮助，赞一个