发现这题真的坑超多啊...调了一晚上终于过了...我好菜啊qwq。
题意说的比较明白，让你求满足(si^k)%(m1^m2)==0的最小k值。然后看数据范围我们知道，我们肯定不能暴力的判断，需要应用到算术基本定理的内容。
我的思路：把m1分解质因数，拆成算术基本定理的形式，再把每个质因数的个数乘上m2.
之后对于每个细胞，我们也将他分解质因数。显然，m1的质因数在si中必须出现，否则消不掉也就不能整除。之后我们找哪个质因数被削掉需要分裂的次数最多，这个次数作为这个细胞的次数。（这里思路有点偏差，算被削掉需要分裂的次数时，是下除上而不是下减上。因为是将si进行乘方。而且还要判断是否能整除，不能整除还要加1）
至于无解的情况，记录一个step，如果每个细胞都有不存在试管质因子的情况，则step++，最后若step==n判定无解。
思路看起来比较清晰的...不过昨天手残导致了许多错误233
现列举如下：
1. 炸内存。原因是在用细胞质因子与试管质因子逐渐逼近时没有判断边界
2. 由于用到 了许多数组，把数组名自己搞混了==
3. 变量名（循环的ij）搞混了4. 分解质因数部分板子敲错了，最后应为(m>1)，否则遇到平方数就会很不好搞
5. 对特殊情况的考虑：m1=1的时候不需要培养时间，答案为0；si=1时这个细胞不可用。
6. 每次检验完一个细胞恢复初值
Code
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 8 int n,cnt,hu; 9 int m1,m2,ans=0x7fffffff,num,step;10 int cell[10090],pm1[10000],cm1[10000],ps[50000],cs[50000];11 bool vis[1000000]; 12 13 void init()14 {15 num=0;16 memset(vis,0,sizeof(vis));17 memset(cs,0,sizeof(cs));18 }19 20 int main()21 {22 // freopen("1.in","r",stdin);23 scanf("%d",&n);24 scanf("%d%d",&m1,&m2);25 if(m1==1) {printf("0");return 0;}26 for(int i=1;i<=n;i++) scanf("%d",&cell[i]);27 for(int i=2;i<=sqrt(m1);i++)28 if(m1%i==0)29 {30 pm1[++cnt]=i,cm1[cnt]=0;31 while(m1%i==0) m1/=i,cm1[cnt]++;32 }33 if(m1>1) pm1[++cnt]=m1,cm1[cnt]++; 34 for(int i=1;i<=cnt;i++) cm1[i]*=m2;35 for(int i=1;i<=n;i++)36 {37 int renew=0;38 int tmp=cell[i];39 if(tmp==1) {step++;continue;}40 bool flag=0;41 for(int j=2;j<=sqrt(tmp);j++)42 if(tmp%j==0)43 {44 vis[j]=1;45 ps[++num]=j,cs[num]=0;46 while(tmp%j==0) tmp/=j,cs[num]++;47 }48 if(tmp>1)49 {50 vis[tmp]=1;51 ps[++num]=tmp;cs[num]++;52 }53 for(int j=1;j<=cnt;j++) if(!vis[pm1[j]]) {step++;flag=1;break;}54 if(flag) {init();continue;}55 int head=1;56 for(int j=1;j<=cnt;j++)57 {58 while(ps[head]!=pm1[j]&&head
* Update 关于复杂度的问题
因为我是把每个细胞分解质因数，所以复杂度可能达到O（n*sqrt(si)），si是2e9级别，n是10000级别。开始我还怀疑了自己的复杂度。
后来经各路dalao指点，发现其实筛出m1的素数那么一搞也行，复杂度就可行了。（可能本题数据太弱所以我也过了？逃）