专栏文章

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

DDiaoHantong
P1069题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miqg4tym
此快照首次捕获于
2025/12/04 04:15
3 个月前
此快照最后确认于
2025/12/04 04:15
3 个月前
查看原文

题目传送门

思路

这道题看似复杂，数据量太大，计算有难度，但是仔细分析会发现，其实只需对 m1m1 进行质因数分解即可。 m1m2m1^{m2} 和 m1m1 含有同样的质因子，只是前者每个质因子出现的次数是后者的 m2m2 倍。而要求出“刚好可以平均分入 mm 个试管 ”的时间 kk，实际上就是要求出最小的正整数 kk，使得存在第 ii 种细胞分裂数 sis_i，满足 siks_i^k 可以整除 m1m2m1^{m2}。
要如何判断整除呢？逐个考虑每个 sis_i，如果有 mm 中有而 sis_i 中没有的质因子，就说明这个 sis_i 经过多少秒都不可能均分；否则就计算 sis_i 和 mm 中每个质因子出现的次数之比，从而求出最多需要多少秒才能整除。最后，在可以均分的 sis_i 中取 kk 最小的一项，就可以得到结果。而假如每一个 sis_i 都不能均分，就输出 −1-1。

代码

CPP
#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;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...