题目描述

Hanks 博士是BT (Bio-Tech，生物技术) 领域的知名专家。现在，他正在为一个细胞实验做准备工作：培养细胞样本。
Hanks 博士手里现在有N 种细胞，编号从1~N，一个第i 种细胞经过1 秒钟可以分裂为Si 个同种细胞（Si 为正整数）。现在他需要选取某种细胞的一个放进培养皿，让其自由分裂，进行培养。一段时间以后，再把培养皿中的所有细胞平均分入M 个试管，形成M 份样本，用于实验。Hanks 博士的试管数M 很大，普通的计算机的基本数据类型无法存储这样大的M 值，但万幸的是，M 总可以表示为m1 的m2 次方，即M =m1m2 ，其中m1，m2 均为基本数据类型可以存储的正整数。
注意，整个实验过程中不允许分割单个细胞，比如某个时刻若培养皿中有4 个细胞，Hanks 博士可以把它们分入2 个试管，每试管内2个，然后开始实验。但如果培养皿中有5个细胞，博士就无法将它们均分入2个试管。此时，博士就只能等待一段时间，让细胞们继续分裂，使得其个数可以均分，或是干脆改换另一种细胞培养。
为了能让实验尽早开始，Hanks 博士在选定一种细胞开始培养后，总是在得到的细胞“刚好可以平均分入M 个试管”时停止细胞培养并开始实验。现在博士希望知道，选择哪种细胞培养，可以使得实验的开始时间最早。

输入描述:

共有三行。
第一行有一个正整数N，代表细胞种数。
第二行有两个正整数，以一个空格隔开，即表示试管的总数M。
第三行有N个正整数，第i个数 表示第i种细胞经过1秒钟可以分裂成同种细胞的个数。

输出描述:

共一行，为一个整数，表示从开始培养细胞到实验能够开始所经过的最少时间（单位为秒）。
如果无论Hanks博士选择哪种细胞都不能满足要求，则输出整数-1。

示例1

输入
1
2 1
3
输出
-1
说明
经过1秒钟，细胞分裂成3个，经过2秒钟，细胞分裂成9个，……，可以看出无论怎么分裂，细胞的个数都是奇数，因此永远不能分入2个试管。

示例2

输入
2
24 1
30 12
输出
2
说明
1种细胞最早在3秒后才能均分入24个试管，而第2种最早在2秒后就可以均分（每试管144/(241)=6个）。故实验最早可以在2秒后开始。

备注:

对于50%的数据，有。
对于所有的数据，有。

解答

这道题就是质因数分解，把如果要把第种细胞变得可以平均分的话，那么中必须得有的所有质因数，而只是给的所有质因数带了一个指数幂，所以只要把直接乘进的质因数个数中就好，然后再把对每一个质因数进行分解，看对每一个质因数要分裂几次，然后最大的那个就是要分裂的次数，不过要注意，这道题第一个数据是个坑，当是1时，任何数都可以，所以直接出0即可
#include<bits/stdc++.h>
#define maxn 10000000
using namespace std;
int a[maxn],b[maxn],pri[maxn];//a是m1中的质因数，b对应得表示质因数的个数，pri就是在a范围内的质数
bool V[maxn];//标记质因数的玩意
int main()
{
    int n,m1,m2;
    scanf("%d%d%d",&n,&m1,&m2);
    if(m1==1)
    {
        printf("0");
        return 0;
    }//坑的数据处理
    memset(V,true,sizeof(V));
    for(int i=2;i*i<=m1;i++)//小于平方根，大家都懂
      if(V[i])
        for(int j=i;i*j<=m1;j++)
          V[i*j]=false;
    int k=0;
    for(int i=2;i<=m1;i++)
      if(V[i])
      {
          pri[++k]=i;
      }
    int x=m1;k=0;
    for(int i=1;pri[i]*pri[i]<=x;i++)
      if(x%pri[i]==0)
      {
          k++;
          a[k]=pri[i];
          while(x%pri[i]==0)
          {
              b[k]++;
              x/=pri[i];
        }
        b[k]*=m2;
      }
    if(x>1)//分解到最后可能会剩余一个质因子 
    {
        a[++k]=x;
        b[k]=m2;
    }//分解m1
    //a[i]是M1^m2的第i种质因子
    //b[i]是m1^m2第i种质因子的个数
    int ans=1<<30;
    for(int i=1;i<=n;i++)
    {
        int si;
        scanf("%d",&si);
        int t=0;
        for(int j=1;j<=k;j++)
        {
            if(si%a[j])//如果不含有相同的质因子，就跳出 
            {
                t=1<<30;
                break;
            }
            int p=0;
            while(si%a[j]==0)
            {
                p++;
                si/=a[j];
            }
            //b[j]是第j种质因子的个数，P是当前细胞该种质因子的个数
            int d=b[j]/p;
            if(b[j]%p)d++; //向上取整，各位大佬也可以用ceil，不过用这个效率高点
            if(d>t)t=d; //更新每个细胞需要分裂的次数
        }
        if(t<ans)ans=t;//更新答案
    }
    if(ans==1<<30)ans=-1;//处理不行的情况
    printf("%d\n",ans);
    return 0;
}



来源：Masterchief