题解 P1069 【细胞分裂】

暗ざ之殇 · 2019-06-20 09:44:36 · 题解

看了好多大佬用的质因数分解来做这个题，我来一发思路不一样的QwQ~

我们看这个数据：m_1的范围是 30000 以内，m_2 的范围是10000 以内，若我们直接求 m_1^{m_2}……，暴的不堪设想；

那么我们就要换一种别的方法喽，当然分解质因数可以，而且这个思路很好，题解里很多大佬详细的讲解了，但是我也说下我的思路啦：

首先我们将每种细胞单独拿出来考虑，就设它是 S_i 吧，那么总有m1^{m2} | Si^n ，这里这个 n 就是要求的最小时间；

然后我们可以考虑求出来 m_1 与 S_i 的最大公约数 gcd_1，因为想到这个 gcd_1 在前面会被算个{gcd_1}^{m2}，在后面又会被算个{gcd_1}^n，觉得有点浪费（当时我真的这么想），就单独将它摘出来吧；

有了最大公约数，我们就可以将m_1^{m_2}和S_i^n转化一下形式啦：

设 m_1=m*gcd_1，S_i=s*gcd_1，那么(m*gcd_1)^{m2} | (s*gcd_1)^n，也就是 m^{m_2}*{gcd_1}^{m_2} | s^n * {gcd_1}^n；

两边同除以 {gcd_1}^{m_2}后得到： m^{m_2} | s^n * {gcd_1}^{n-m_2}；

我们继续看左边这个东东，它是不是很像原来我们一开始列出的式子：

我们可以将 n-m_2 看成一个整体，这样就真的和我们一开始列出的式子很像了QwQ

所以我们还可以继续进行我们刚刚执行的操作：找最大公约数！

恩，继续找最大公约数：

我们设 gcd_2=gcd \ (m,gcd_1)，则 m = {gcd_2} * mm，gcd_1=gcd_2 * ggcd_1 （有点混，但是真的找不出来好变量名了，gcd_2 是最大公约数，mm 是 m 除以最大公约数后剩下的数，ggcd_1 是 gcd_1 除以最大公约数后剩下的数）；

还是刚刚那样，用最大公约数将原先的 m 和 gcd_1 表示出来：

=(gcd_2 * mm)^{m_2} | (gcd_2 * ggcd_1)^{n-m_2}

={gcd_2}^{m_2} mm^{m_2} | ${gcd_2}^{n-m_2} {ggcd_1}^{n-m_2}$

然后我们还是把最大公约数那一项除到右边来：

=mm^{m_2} | {gcd_2}^{n-m_2-m_2}* {ggcd_1}^{n-m_2}

=mm^{m_2} | {gcd_2}^{n-2 * m_2}* {ggcd_2}^{n-m_2}

还是再套用上面的定理：

那么式子又简化为： mm^{m_2} | {gcdd_2}^{n-2 * m_2}

然后我们还可以找最大公约数…………，有没有发现其实这就是一个递归操作，那有没有界限呢？

当然有！我们上述的操作其实就是一直将 m_1 除以某个数，那么最后它一定会被除到 1 的！这样一来，式子就成了：

那么我们先列出一个粗略的式子：

首先求出 gcd（96，36）=12，然后将最大公约数代入原式：

然后我们将最大公约数 12 那一项除到右边：

将最大公约数 4 的那一项除到右边：

你是不是已经知道了？把最大公约数 2 那一项除过去：

哇！我们将左边的 m_1 给搞成 1 了耶，接下来的任务不就是求最小的 n 使得2^{n-25}是整数了嘛？

其实它和最后的答案 n 有关，我们再来找一下 m_2 的规律：

接下来这个例子我们不再将m_2带进去了，这样能更好的找到规律哦：

列出式子 m_1^{m_2} | S_1^n：

将m_1，S_1代入得： 32^{m_2} | 56^n；

第一次循环：

首先拆括号： n-t * m_2 + { tot * [ n-(t * m_2-m_2)] }

我们将 n 放在左边，m_2 放在右边，于是我们得到：

提取公因式： (1+tot)* n =m_2 * (t + t * tot -tot)

最后我们将 n 的系数化 1，就得到了答案：

我们已经把 s 和 q 的公共部分 gc 全部都分离出来了，那么剩下的 s / gc 和 q / gc 一定都与 gc 互质，这其实又转化成了第一种情况；

所以我们只需要将 gc 的指数搞成 0 就好了：

令 gc 的指数为 0：

-----将有关 m_2 的项移到右边

------提取公因式

------n 系数化 1

所以这种情况的公式我们也推出来了，所以这个题我们就做完了QwQ~

                if((t*m2*tots+totq*(t-1)*m2)%(tots+totq)==0)    //这种情况的公式，注意向上取整 
                   ans=(t*m2*tots+totq*(t-1)*m2)/(tots+totq);   
                else ans=(t*m2*tots+totq*(t-1)*m2)/(tots+totq)+1;

下面就是完整代码啦：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int read()                            //读入优化 
{
    char ch=getchar();
    int a=0,x=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') x=-x;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        a=(a<<3)+(a<<1)+(ch-'0');
        ch=getchar();
    }
    return a*x;
}
int n,m1,m2,minx,gcdd,m,s,q,t,flag,tot,ans,tots,totq;        //t代表q能分解成多少个s         
int S[10001];
int gcd(int a,int b)                  //欧几里得算法求最大公约数 
{
    if(b==0) return a;
    else return gcd(b,a%b);
}
int main()
{
    n=read();
    m1=read();
    m2=read();
    minx=1e9;
    if(m1==1)                             //这里一定要注意特判m1==1的情况，不然会TLE 
    {
        cout<<0;                          //无需等待，因为任何数都是1的倍数 
        return 0;
    }
    for(int i=1;i<=n;i++) S[i]=read();
    for(int i=1;i<=n;i++)                 
    {
        tot=0;
        m=m1;                             //拷贝一份m1的值
        s=S[i];                           //拷贝一份S[i]的值 
        flag=1;                           //判断是否有解 
        t=0;                              //记录最大公约数要减几个m2 
        while(m!=1)
        {
            gcdd=gcd(m,s);                //第一小步，求最大公约数 
            if(gcdd==1) {flag=0;break;}   //如果互质，那么肯定无解，直接跳出 
            m/=gcdd;                      //左边剩下了m/gcdd 
            q=s/gcdd;                     //q就是s除以gcdd后剩下的数 
            s=gcdd;                       //右边剩下了gcdd         
            t++;                          //每进入一次循环，就要多减1个m2   
        } 
        if(flag)
        {
            int gc=gcd(q,s);        //先求出gcd(q,s) 
            if(gc!=1&&gc!=s)        //单独讨论第三种情况 
            {
                totq=0;tots=0;      //注意清空 
                while(q%gc==0)      //如果q中含有gc就分离 
                {
                    totq++;         //q中含有gc的个数 
                    q/=gc;
                }
                while(s%gc==0)      //如果s中含有gc就分离 
                {
                    tots++;         //s中含有gc的个数 
                    s/=gc;
                }
                if((t*m2*tots+totq*(t-1)*m2)%(tots+totq)==0)    //这种情况的公式，注意向上取整 
                   ans=(t*m2*tots+totq*(t-1)*m2)/(tots+totq);   
                else ans=(t*m2*tots+totq*(t-1)*m2)/(tots+totq)+1;
                minx=min(minx,ans);
            }
            else                   //第一，二种情况 
            {
                while(q%s==0)      //如果q里面含有s，分离出来 
                {
                    tot++;         //tot表示能分离出来多少个s，第一种情况就是tot=0的情况 
                    q/=s;           
                }
                if((t*m2+tot*(t-1)*m2)%(tot+1)==0)    //我不知道为什么ceil出来的答案不对，只能自己模拟向上取整了 
                   ans=(t*m2+tot*(t-1)*m2)/(tot+1);   //没余数说明正好整除 
                else ans=(t*m2+tot*(t-1)*m2)/(tot+1)+1;//如果有余数就要+1(这个1就是余数除成小数后再向上取整后得到的) 
                minx=min(minx,ans);        //题目要求整体最小时间 
            }
        }
    }
    if(minx==1e9) cout<<-1;        //如果minx没被更新，说明无解 
    else cout<<minx;
    return 0;
} 

这种思路我也不知道是不是正解 QwQ, 如果有误请指出，我会认真完善的~

觉得这个思路比较不错的就点个推荐呗~~~

感谢你的观看QwQ~