还是不难的,问题出在循环和函数
你看:
对于 50%的数据,有m_1^{m_2} ≤ 30000m 1 m 2
≤30000。
对于所有的数据,有1 ≤N≤ 10000,1 ≤m_1 ≤ 30000,1 ≤m_2 ≤ 10000,1 ≤ S_i ≤ 2,000,000,0001≤N≤10000,1≤m 1
≤30000,1≤m 2
≤10000,1≤S i
≤2,000,000,000。
你连%50都没有达到还谈什么AC
改成这样
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool prime(int x){//线性筛质数
if(x==1)return 0;
if(x==2||x==3)return 1;
if(x%6!=1&&x%6!=5)return 0;
int temp=sqrt(x);for(int i=5;i<=temp;i+=6)if(x%i==0||x%(i+2)==0)return 0;
return 1;
}
inline int work(int x,int y){//判断是否整除,如整除输出商,否则输出商+1
if(x%y==0)return x/y;
else return x/y+1;
}
const int maxn=1e5+10;
int n;
int m1,m2;
int s[maxn];
int sum_m[maxn],sum_cell[maxn];//下标为第i个质数,sum_m为m分解质因数后的指数,sum_cell为s[i]分解质因数后的质数
int pr[maxn];
int tot=1,sum_pr;
bool opt,flag;
int ans,minn=1<<30;
int main(){
cin>>n>>m1>>m2;
if(m1==1){puts("0");return 0;}
for(int i=1;i<=n;i++)cin>>s[i];
for(int i=2;i<=100000;i++)if(prime(i))++sum_pr,pr[sum_pr]=i;//统计质数个数,把质数搞出来
while(m1!=1){//把m分解质因数
if(m1%pr[tot]==0){
while(m1%pr[tot]==0)
sum_m[tot]++,m1/=pr[tot];
}
sum_m[tot]*=m2;//小技巧,前文提到过
++tot;
}
for(int i=1;i<=n;i++){
bool flag=false;tot=1,ans=-1;
memset(sum_cell,false,sizeof(sum_cell));//注意清空数组
while(s[i]!=1){//为s[i]分解质因数
if(s[i]%pr[tot]==0){
while(s[i]%pr[tot]==0)
sum_cell[tot]++,s[i]/=pr[tot];
}
++tot;
}
for(int j=1;j<=sum_pr;j++){
if(sum_m[j]&&!sum_cell[j])flag=true;//如果没有完全包含,这个s[i]的答案就为-1
if(sum_m[j]&&sum_cell[j])ans=max(ans,work(sum_m[j],sum_cell[j]));//如果完全包含,计算即可
}
if(!flag){opt=true;minn=min(minn,ans);}//取最大值
}
if(opt)printf("%d",minn);//只要有能整除的就输出
else puts("-1");//如果所有的细胞都不行,就无解输出-1
return 0;
}
```
解释在程序里
by Dsesert @ 2020-08-31 19:27:49
我建议你照我的改一下,模拟那部分可以改这题主要就是模拟,其他没什么难的=-=这是模拟和数学的方法,你还可以用搜索做(记忆化搜索)你的可能会超时,,要达到这个1 ≤N≤ 10000,1 ≤m_1 ≤ 30000,1 ≤m_2 ≤ 10000,1 ≤ S_i ≤ 2,000,000,0001≤N≤10000,1≤m 1 ≤30000,1≤m 2 ≤10000,1≤S i ≤2,000,000,000。想改挺难得
要大规模改动。。
by Dsesert @ 2020-08-31 19:30:18