题解：P1069 [NOIP2009 普及组] 细胞分裂

· · 题解

题目传送门

思路

这道题看似复杂，数据量太大，计算有难度，但是仔细分析会发现，其实只需对 m1 进行质因数分解即可。 m1^{m2} 和 m1 含有同样的质因子，只是前者每个质因子出现的次数是后者的 m2 倍。而要求出“刚好可以平均分入 m 个试管 ”的时间 k，实际上就是要求出最小的正整数 k，使得存在第 i 种细胞分裂数 s_i，满足 s_i^k 可以整除 m1^{m2}。

要如何判断整除呢？逐个考虑每个 s_i，如果有 m 中有而 s_i 中没有的质因子，就说明这个 s_i 经过多少秒都不可能均分；否则就计算 s_i 和 m 中每个质因子出现的次数之比，从而求出最多需要多少秒才能整除。最后，在可以均分的 s_i 中取 k 最小的一项，就可以得到结果。而假如每一个 s_i 都不能均分，就输出 -1。

代码

#include<bits/stdc++.h>
using namespace std;
int m1,m2,s[10001],k=0x7fffffff;
int prime[30010],cnt[30010];
int decompose(int n){//分解质因子
    int m=0;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0){
            prime[++m]=i;
            cnt[m]=0;
            while(n%i==0){
                n/=i;
                cnt[m]++;
            }
        }
    }
    if(n>1){
        prime[++m]=n;
        cnt[m]=1;
    }
    //m的质因子需要在m1的基础上每项乘m2
    for(int i=1;i<=m;i++)cnt[i]*=m2;
    return m;
}
int main(){
    int n;
    cin>>n>>m1>>m2;
    for(int i=1;i<=n;i++)cin>>s[i];
    if(m1==1){cout<<"0";return 0;}
    int mz=decompose(m1);
    for(int i=1;i<=n;i++){
        int ans=0;//记录选第i种细胞的时间
        for(int j=1;j<=mz;j++){
            //若不能整除,则无解
            if(s[i]%prime[j]){ans=0x7fffffff;break;}
            int c=0;
            //求出质因子在s[i]中出现的次数c
            while(!(s[i]%prime[j]))s[i]/=prime[j],c++;
            //若不能整除，则多一秒
            int tmp=cnt[j]%c==0?0:1;
            ans=max(ans,cnt[j]/c+tmp);
        }
        //记录最小的秒数
        k=min(k,ans);
    }
    cout<<(k==0x7fffffff?-1:k);
    return 0;
}