题解 P1069 【细胞分裂】

· · 题解

很考查基础的一道数论题

这道题的思路楼上的大佬已经讲的很清楚了：

先把试管的数量m1分解质因数

再把每一种细胞的个数s分解质因数

比较一下两者的质因数，看看s的质因数是否包含m1的所有质因数

包含：更新答案

不包含：继续循环

那我们就要思考一下细节了

还是有一点思维难度的（尤其是考场上）

首先，如何分解质因数？

这是第一道坎，我们考虑一下这样一个问题：需要完全分解s吗？

答案是不需要！

为什么？

想一想我们分解s的初衷：判断能否整除并计算所需时间

举个例子：

试管数为10，细胞数为30

6=2*3,30=2*3*5

我们判断的话只会用到6的两个质因数2,3

5还需要分解出来吗？ 显然不需要，让它待在那就行了

因此，我们对于s，只需用m1的质因数将它进行部分分解

还有，怎样记录质因数和次数？

有两种选择：

第一种选择类似于广搜存坐标的方法

即用两个一维数组，把它们对齐

一旦分解到一个质因数，就把该质因数和其次数分别存到两个数组里

第二种选择是用map和vector

vector存质因数，map则建立由质因数到次数的映射

逛了一圈都没发现有人用map，那我就用map了

另外，有一个注意点：

当m1=1时，直接输出0

想到了这些，这道题目就顺利的AC了

代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>//map库 
#include<vector>//vector库 
#define maxx 0x7fffffff//这是int的最大值 
using namespace std;
map<long long,long long> a1;//建立m1的质因数到次数的映射
vector<long long> x1;//存放m1质因数
bool su(long long k){//素数判断函数 
    for(int i=2;i*i<=k;++i){
        if(k%i==0) return 0;
    }
    return 1;
}
int main(){
    long long n,m1,m2,ans=maxx,t1,t2,time,l2,l1,cnt1;//time表示单个细胞的时间,ans为最终答案 
    long long s;
    bool flag2=0;//flag2用来标记是否有解
    cin>>n>>m1>>m2;
    if(m1==1){//是1，直接输出0就完事 
        cout<<0;
        return 0;
    }
    if(su(m1)){//它是个素数，不用分解了 
        a1[m1]=m2;
        x1.push_back(m1);
        l1=1;
    }
    else{//是合数 
        t1=m1;//找个替身 
        for(int i=2;i*i<=t1;++i){//枚举可能的因子 
            if(m1%i!=0) continue;//不是因子，继续枚举 
    //好啊，避开了continue，能做到这一点的只有质因数 
            x1.push_back(i);//压进去！ 
            while(m1%i==0){//不断循环，榨干它！ 
                a1[i]++;//每循环一次，次数+1 
                m1/=i;
            }
            a1[i]*=m2;//别把m2忘了 
        }
        l1=x1.size();//取大小 
    }
    for(int i=1;i<=n;++i){//开始输入细胞数量s 
        scanf("%lld",&s);
        time=0;//每种细胞所花时间 
        t2=s;//还是替身 
        for(int j=0;j<l1;++j){
            if(t2%x1[j]!=0){//不包含！ 
                goto here;//goto语句踢出去 
            }
            cnt1=0;//只需要保存单个质因数的次数 
            while(t2%x1[j]==0){
                t2/=x1[j];
                cnt1++;
            }       
            int tt=ceil(a1[x1[j]]*1.0/cnt1);//取分裂次数(向上取整) 
            if(tt>time) time=tt;//更新time 
        }
        flag2=1;//没有被踢，就是有解 
        if(time<ans) ans=time;//更新答案 
        here: continue;//一脚踢到这里，啥事也没 
    }
    if(flag2) cout<<ans;//有解，输出ans 
    else cout<<-1;//无解，输出-1 
    return 0;//后话：这题是个数论题 
}

你AC了没？AC了就给个赞呗