[NOIp2009普及组]细胞分裂

思路：

首先将$30000$以内的所有质数求出，再对$m1$质因数分解。
对于每个$s$，计算它和$m1$的每个公共质因数的倍数关系，取$max$则为该细胞满足条件所花费的最少时间。
再对于每个细胞的最小时间取$min$，即为所求的结果。
注意特判$m1=1$和$m2=0$的情况。

 #include<cmath>

 #include<cstdio>

 #include<cctype>

 #include<vector>

 inline int getint() {

     char ch;

     while(!isdigit(ch=getchar()));

     int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int inf=0x7fffffff;

 std::vector<int> prime;

 inline bool isPrime(const int x) {

     for(unsigned i=;i<prime.size();i++) {

         if(prime[i]>sqrt(x)) break;

         if(!(x%prime[i])) return false;

     }

     return true;

 }

 const int M1=;

 int p[M1];

 int main() {

     int n=getint(),m1=getint(),m2=getint();

     if(m1==||!m2) {

         puts("");

         return ;

     }

     for(int i=;i<M1;i++) {

         if(isPrime(i)) {

             prime.push_back(i);

         }

     }

     for(unsigned i=;m1!=;i++) {

         while(!(m1%prime[i])) {

             p[i]+=m2;

             m1/=prime[i];

         }

     }

     int ans=inf;

     while(n--) {

         int s=getint(),tmp=;

         for(unsigned i=;i<prime.size();i++) {

             if(!p[i]) continue;

             int cnt=;

             if(s%prime[i]) goto Next;

             while(!(s%prime[i])) {

                 cnt++;

                 s/=prime[i];

             }

             tmp=std::max(tmp,(p[i]-)/cnt);

         }

         ans=std::min(ans,tmp);

         Next:;

     }

     printf("%d\n",ans==inf?-:ans+);

     return ;

 }