题解

#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>//map库
#include<vector>//vector库
#define maxx 0x7fffffff//这是int的最大值
using namespace std;
map<long long,long long> a1;//建立m1的质因数到次数的映射
vector<long long> x1;//存放m1质因数
bool su(long long k){//素数判断函数
for(int i=2;ii<=k;++i){
if(k%i0) return 0;
}
return 1;
}
int main(){
long long n,m1,m2,ans=maxx,t1,t2,time,l2,l1,cnt1;//time表示单个细胞的时间,ans为最终答案
long long s;
bool flag2=0;//flag2用来标记是否有解
cin>>n>>m1>>m2;
if(m11){//是1，直接输出0就完事
cout<<0;
return 0;
}
if(su(m1)){//它是个素数，不用分解了
a1[m1]=m2;
x1.push_back(m1);
l1=1;
}
else{//是合数
t1=m1;//找个替身
for(int i=2;ii<=t1;i){//枚举可能的因子
if(m1%i!=0) continue;//不是因子，继续枚举
//好啊，避开了continue，能做到这一点的只有质因数
x1.push_back(i);//压进去！
while(m1%i==0){//不断循环，榨干它！
a1[i];//每循环一次，次数+1
m1/=i;
}
a1[i]*=m2;//别把m2忘了
}
l1=x1.size();//取大小
}
for(int i=1;i<=n;++i){//开始输入细胞数量s
scanf("%lld",&s);
time=0;//每种细胞所花时间
t2=s;//还是替身
for(int j=0;j<l1;j){
if(t2%x1[j]!=0){//不包含！
goto here;//goto语句踢出去
}
cnt1=0;//只需要保存单个质因数的次数
while(t2%x1[j]==0){
t2/=x1[j];
cnt1;
}
int tt=ceil(a1[x1[j]]*1.0/cnt1);//取分裂次数(向上取整)
if(tt>time) time=tt;//更新time
}
flag2=1;//没有被踢，就是有解
if(time<ans) ans=time;//更新答案
here: continue;//一脚踢到这里，啥事也没
}
if(flag2) cout<<ans;//有解，输出ans
else cout<<-1;//无解，输出-1
return 0;//后话：这题是个数论题
}