1 条题解

  • 0
    @ 2025-8-24 21:20:35

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar 暗ざ之殇
    你要记得，紫檀未灭，我亦未去。

    搬运于2025-08-24 21:20:34，当前版本为作者最后更新于2019-06-20 09:44:36，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

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

    我们看这个数据：m1m_1的范围是 3000030000 以内，m2m_2 的范围是1000010000 以内，若我们直接求 m1m2m_1^{m_2}……，暴的不堪设想；

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

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

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

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

    设 m1=m∗gcd1m_1=m*gcd_1，Si=s∗gcd1S_i=s*gcd_1，那么(m∗gcd1)m2∣(s∗gcd1)n(m*gcd_1)^{m2} | (s*gcd_1)^n，也就是 mm2m^{m_2}*gcd1m2{gcd_1}^{m_2} | sns^n *gcd1n {gcd_1}^n；

    两边同除以 gcd1m2{gcd_1}^{m_2}后得到： mm2∣sn∗gcd1n−m2m^{m_2} | s^n * {gcd_1}^{n-m_2}；

    我们继续看左边这个东东，它是不是很像原来我们一开始列出的式子：
    m1m2m1^{m_2} | SinSi^n 与 mm2 m^{m_2} | sns^n * gcd1n−m2 {gcd_1}^{n-m_2} ；

    虽然只是有一点点像啦，但是这右边差的有点大啊qwqqwq，能不能化简一下啦？

    当然能！我们看一个定理：

    若有两个互质的数 p,qp,q，则一定存在 pnp^n % qmq^m ≠0≠ 0（其实是 gcdgcd（pnp^n，qmq^m）=1=1） ，其实就是无论多少次方都不能整除！

    草草证明一下吧：

    ∵∵ pp，qq 互质

    ∴p∴p 和 qq 无任何相同的因子

    又∵∵ pnp^n 和 qmq^m 只是改变了因子的指数，而并没有增加或减少因子本身的数值

    ∴∴ 仍没有相同的因子，即仍互质

    有了这个定理，我们就可以化简右边的一大堆式子了：

    因为 mm 和 ss 是分别由 m1m_1 和 SiS_i 同除以它们的最大公约数 gcd1gcd_1 得到，那么 mm 和 ss 一定是互质的！（所有相同的因子都被除了，只剩下不相同的了）

    那么也就是说，右边的 sns^n 无论如何都不能使 mm2m^m2 | sns^n，答案只可能从上面的gcd1n−m2{gcd_1}^{n-m_2}中产生！所以我们完全可以舍弃sns^n来化简式子，那么式子就化简成：

    mm2m^{m_2} | gcd1n−m2{gcd_1}^{n-m_2}

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

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

    恩，继续找最大公约数：

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

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

    mm2m^{m_2} | gcd1n−m2{gcd_1}^{n-m_2}

    =(gcd2∗mm)m2(gcd_2 * mm)^{m_2} | (gcd2∗ggcd1)n−m2(gcd_2 * ggcd_1)^{n-m_2}

    =gcd2m2{gcd_2}^{m_2} * mmm2 mm^{m_2} | gcd2n−m2∗ggcd1n−m2{gcd_2}^{n-m_2}* {ggcd_1}^{n-m_2}

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

    =mmm2mm^{m_2} | gcd2n−m2−m2∗ggcd1n−m2{gcd_2}^{n-m_2-m_2}* {ggcd_1}^{n-m_2}

    =mmm2∣gcd2n−2∗m2∗ggcd2n−m2mm^{m_2} | {gcd_2}^{n-2 * m_2}* {ggcd_2}^{n-m_2}

    还是再套用上面的定理：

    ∵mm∵mm与 ggcd2ggcd_2 互质，那么我们可以舍弃 ggcd2n−m2{ggcd_2}^{n-m_2}

    那么式子又简化为： mmm2∣gcdd2n−2∗m2mm^{m_2} | {gcdd_2}^{n-2 * m_2}

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

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

    1m21^{m_2} | …………，对没错，1m21^{m_2}还是 11，那么这个问题就被我们巧妙的转化成了：

    求最小的 nn，使得右边那一堆式子是整数！（是不是很神奇啊！）

    我们来一组详细的数字来认真得体会上面的过程：

    m1=96m_1=96，m2=5m_2=5

    S1=36S_1=36

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

    m1m2∣S1n{m_1}^{m_2} | S1^n（这个n和题目中的 nn 不一样，这个 nn 就是我们要求的最短时间），代入数据就是：965∣36n96^5 | 36 ^n

    首先求出 gcdgcd（9696，3636）=12=12，然后将最大公约数代入原式：

    (12∗8)5∣(12∗3)n(12 * 8)^5 |( 12* 3)^n = 12512^5 * 858^5|12n∗3n 12^n * 3^n

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

    858^5 | 12n−5∗3n12^{n-5} * 3^n，运用定理可知 3n3^n 不可能产生答案，我们可以舍弃它：

    858^5 | 12n−512^{n-5}，我们继续找到 gcdgcd（88 , $12）2）=4$，并代入原式：

    (4∗2)5(4*2)^5 | (4∗3)n−5(4*3)^{n-5}=45∗25∣4n−5∗3n−54^5 * 2^5| 4^{n-5}* 3^{n-5}

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

    25∣4n−10∗3n−52^5 | 4^{n-10}* 3^{n-5}，运用定理可知3n−53^{n-5}不可能产生答案，我们可以舍弃它：

    25∣4n−102^5 | 4^{n-10}，我们继续找到 gcdgcd（22 , 44）=2=2，并代入原式：

    (1∗2)5∣(2∗2)n−10(1 * 2)^5 | (2 * 2)^{n-10}=15∗251^5 * 2^5|2n−10∗2n−10 2^{n-10}* 2^{n-10}

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

    15∣2n−15∗2n−101^5 | 2^{n-15}* 2^{n-10} = 1∣22n−25 1 | 2^{2n-25}

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

    It is so easyIt \ is\ so\ easy！ 列出不等式 22n−25>=202^{2n-25}>=2^0，则(2n−25)>=0(2n-25)>=0，解得最小的整数 n=13n=13

    SoSo 我们接下来总结一下我们每一步的操作，方便总结规律然后写代码：

    1.1.求出m1m_1和SiS_i的最大公约数 gcdgcd（m1m_1,SiS_i);

    2.2.若gcd=1gcd=1，说明这两个数互质，则不可能有解，直接跳出；

    3.3.将 m1m_1 和 SiS_i 用这个最大公约数表示出来，然后将左侧的最大公约数除到右侧去；

    4.4.可以舍弃与左侧互质的部分，其实也就是 Si/gcdS_i / gcd 后的数；

    5.5.从第一步开始继续重复上述操作，直到gcd=1gcd=1 或 m1=1m_1=1；

    你会发现我们上述操作始终和 m2m_2 没啥事，但是它不可能是来打酱油的吧QwQ QwQ~

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

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

    m1=32m_1=32， m2m_2 ，S1=56S_1=56

    列出式子 m1m2m_1^{m_2} | S1nS_1^n：

    将m1m_1，S1S_1代入得： 32m2∣56n32^{m_2} | 56^n；

    第一次循环：

    1.1.求出gcdgcd（3232，5656）=8=8；

    2.gcd2.gcd 不为 11，说明目前阶段有解；

    3.3. 原式 = (8∗4)m2∣(8∗7)n(8 * 4)^{m_2} | (8 * 7)^n ------用最大公约数表示

    = 8m2∗4m2∣8n∗7n8^{m_2} * 4^{m_2}| 8^n*7^n ------拆括号

    =4m2∣8n−m2∗7n4^{m_2} | 8^{n-m_2} * 7^n ------将最大公约数那一项除到右侧

    4.舍弃与 4m24^{m_2}互质的那一项：7n7^n，原式成为：4m2∣8n−m24^{m_2} | 8^{n-m_2}；

    第二次循环：

    1.1.求出gcdgcd（4,84,8）=4=4；

    2.gcd2.gcd 不为 11，说明目前阶段有解；

    3.3. 原式 = (4∗1)m2∣(4∗2)n−m2(4 * 1)^{m_2} | (4 * 2)^{n-m_2} ------用最大公约数表示

    = 4m2∗1m2∣4n−m2∗2n−m24^{m_2} * 1^{m_2}| 4^{n-m_2} * 2^{n-m_2} ------拆括号

    =1m2∣4n−m2−m2∗2n−m21^{m_2} | 4^{n-m_2-m_2} * 2^{n-m_2} ------将最大公约数那一项除到右侧

    =1∣4n−2∗m2∗2n−m21 | 4^{n-2 * m_2}* 2^{n-m_2}

    4.4. 左侧我们已经除到 11 了，那么我们就跳出，分析答案产生；

    不知道各位在刚刚的例子中有没有发现有关 m2m_2 的规律，来和我发现的规律对比一下哪个更好：

    1.1. 我们在第 33 步操作结束以后（就是将最大公约数那一项除过去后），右侧最大公约数的那一项的指数都会减去 m2m_2 是吧，如果我们单独拿出来每一个循环的话，我们可以发现：右侧最大公约数那一项的指数它减去的 m2m_2 的个数是和当前这是第几大步是相同的（其实这个很好理解，我们每一个大步 ss 的指数只减去 11 个m2m_2，但是却非常重要）；

    我们可以来记录进入了几次循环来判断右侧最大公约数 ss 那一项的指数减了几个m2m_2，在代码中用 tt 来记录；

            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   
        }

    2.2.同时它后面的 qq 那一项的指数减去的 m2m_2 的个数是 t−1t-1；

    3.3.我们可以根据 m2m_2 来求解最后的答案；

    4.4.一个不是关于 m2m_2 的规律（实在不知道要往哪放但是没有这个总结代码可能看不懂）：

    结合上面的例子，再感性理解一下，我们将左边的最大公约数除到右边后，左边只剩下了m1/gcdm_1 / gcd，而右边呢？由于Si/gcdS_i / gcd 后与 m1/gcdm_1 / gcd 互质，就被抛弃了QwQ QwQ~，所以右边只剩下了最大公约数 gcdgcd，SoSo 进行下一大步操作的就是 m1/gcd∣gcdm_1 / gcd | gcd（这里省略了指数方便理解） ，也就是说：我们令 m1=m1/gcdm_1=m_1 / gcd，Si=gcdS_i = gcd 就可以进行下一大步操作了；

    讲完了 m2m_2 的规律后，我们就可以将上面的步骤转化成代码啦（其实很短）：

            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   
        }

    下面就要动动脑筋仔细思考小细节了：

    当然这个将 m1m_1 除到 11 的过程是没有锅的吧，那么哪里还需要注意呢？

    就是最后的求 nn 的过程了！其实不知道小伙伴们有没有看出来我前面的例子中求 nn 总是很含糊（因为还没讲到这里鸭），所以我就要帮帮带着疑惑看下来的小伙伴们仔细得考虑一下下：

    假设我们已经分解到了最后一步，也就是m1m_1已经被我们除到1了，那么右边的式子我们就可以写成：

    sn−t∗m2∗qn−(t−1)∗m2s^{n - t * m_2} * q^{ n - (t-1) * m_2 } ------（这里ss，qq，tt 的含义和上面代码中的含义相同，还有这里表示指数用了上面总结的公式，不懂得小伙伴可以再回到上面看看）

    那么无非有这 33 种情况：

    1. ss 与 qq 互质，也就是 gcdgcd（ss，qq）=1=1，这时候n=t∗m2n = t * m_2；

    WhyWhy？因为这时候我们要保证右边那一坨式子最后算出来是个整数，而且这两个数还是互质的，所以若有一个是分数的话，另外一个数无论多少次方都不会把它乘成整数的qwqqwq，所以我们要保证这两个数 ss 和 qq 的指数都要>=0>=0，因为我们考虑到 ss 的指数比qq 的指数多减了个 m2m_2，所以我们把 ss 的指数搞成00 的话，qq 的指数一定 >0>0（显然这时候指数为 m2m_2），所以我们只考虑将 ss 的指数弄成 00 就好啦，显然这时候 n=t∗m2n=t * m_2；

    2.gcd12.gcd_1 是 qq 的因数，也就是 gcdgcd（ss，qq）=gcd1=gcd_1，

    这时候 n=ceil[(t+(t−1)∗tot]∗m2/(tot+1))n = ceil [(t+(t-1) * tot ] * m_2 / (tot+1))，tottot 是 qq内含 ss 的个数；

    为什么还要把这种情况单独考虑呢？如果我们像第一种情况只考虑ss的指数的话，直接 n=t∗m2n=t * m_2 ？NONO！因为既然 qq 是 ss 的倍数，那么必然我们将 qq 进行分解质因数的话，里面会有 ss（但是指数不同），那么我们将s进行合并的话，指数不再是 n−t∗m2n-t * m_2了，那是多少呢？------取决于 qq 里面含有多少个 ss！

    这是将 qq 里面所有 ss 全部分离出来的代码：

                    while(q%s==0)      //如果q里面含有s，分离出来 
                {
                    tot++;         //tot表示能分离出来多少个s，第一种情况就是tot=0的情况 
                    q/=s;           
                }

    为了区分，我们将分离出来的 ss 叫做 _ ss，很显然 ss 和 _ ss 的指数不同是吧，那么我们考虑 _ ss 的指数是多少?

    由于它是从 qq 中分离出来的，那么显然 _ ss 和 qq 的指数是相同的，看到上面 qq 的指数是[n−(t−1)∗m2][ n - (t-1) * m_2 ]，那么 _ ss 的指数也是[n−(t−1)∗m2][ n-(t-1) * m_2 ]；

    那么我们是不是可以将 ss 和 _ ss 合并起来鸭？（底数相同不就可以合并嘛？）

    合并后的 ss 的指数就是 [n−(t∗m2)]+[ n-(t * m_2) ]+ tot∗[n−(t−1)∗m2]{ tot * [n-(t-1) * m_2] } ，简单一记就是：11 个 ss 的指数 +tot+tot 个 _ss 的指数；

    再想想哈~我们将 qq 所有的 ss 都分解出来了，那么剩下的东东就和 ss 互质了~ 所有这不就又变成了第一种情况了？

    还是老样子，我们只要使得 ss 的指数为 00 就是解了。

    所以我们要解这个方程：[n−(t∗m2)]+tot∗[n−(t−1)∗m2]=0[ n-(t * m_2) ]+{ tot * [n-(t-1) * m_2] } = 0

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

    =n−t∗m2+tot∗(n−t∗m2+m2)=n- t * m_2 + { tot * ( n - t * m_2 + m_2) }

    =n−t∗m2+tot∗n−t∗m2∗tot+m2∗tot=n - t * m_2 + tot * n - t * m_2 * tot + m_2* tot

    =0=0

    我们将 nn 放在左边，m2m_2 放在右边，于是我们得到：

    n+tot∗n=t∗m2+t∗m2∗tot−m2∗totn + tot * n = t * m_2 +t * m_2 * tot - m_2 * tot

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

    (1+tot)∗n=m2∗[t+tot∗(t−1)](1+tot) * n = m_2 * [ t + tot * (t -1) ]

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

    n=m2∗[t+tot∗(t−1)]/(1+tot)n = m_2 * [ t + tot * (t -1) ] /(1+tot)

    SoSo 这种情况的 nn 我们也搞定了（哎，有没有发现其实第一种情况就是 tot=0tot=0 的情况耶，我们完全可以将第一，二中情况合起来写）

    代码如下：

                    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);        //题目要求整体最小时间

    3.gcd3.gcd（ss，qq）≠1≠1，gcd1gcd_1 ；

    这是什么意思呢？就是当 ss 和 qq 既不互质，也不是倍数关系的时候；

    这种情况有什么魔力呢？你看如果我们用第二种情况的公式的话，显然 tot=0tot=0（qq 不是 ss 的倍数），但是我们注意到 gcdgcd（ss，qq）≠1≠ 1，那么说明它们还有公共部分！

    显然这个公共部分就是 gcdgcd（ss，qq），暂且记为 gc=gcdgc=gcd（ss，qq），所以我们要像第二种情况中的 qq 分离 ss 一样，分别将 ss 和 qq 中的 gcgc 分离出来（逃 ；

    分离的过程和上面几乎一样：

                    while(q%gc==0)      //如果q中含有gc就分离 
                {
                    totq++;         //q中含有gc的个数 
                    q/=gc;
                }
                while(s%gc==0)      //如果s中含有gc就分离 
                {
                    tots++;         //s中含有gc的个数 
                    s/=gc;
                }

    SoSo 我们就从 ss 中分离出了 totstot_s 个 gcgc，从 qq 中分离出了 totqtot_q 个 gcgc，当然这两部分 gcgc 的指数是不同的；

    其中 totstot_s 个 gcgc 的指数是和 ss 的指数相同，均为 n−t∗m2n - t * m_2；totqtot_q 个 gcgc 的指数是和 qq 的指数相同，均为 n−(t−1)∗m2n - (t -1)* m_2 ；

    然后我们将所有 gcgc 的指数合并（就是 totstot_s 个 gcgc 和 totqtot_q 个 gcgc 的指数和）：

    tots∗(n−t∗m2)+totq∗[n−(t−1)∗m2]tot_s * (n - t * m_2)+tot_q * [ n -(t-1)* m_2 ]

    $=tot_s * n - tot_s * t * m_2 + tot_q * n - tot_q * m_2 * (t-1)$

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

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

    令 gcgc 的指数为 00：

    $tot_s * n - tot_s * t * m_2 + tot_q * n - tot_q * m_2 * (t-1)=0$

    $tot_s * n + tot_q * n = tot_s * t * m_2 + tot_q * m_2 * (t-1)$
    -----将有关 m2m_2 的项移到右边

    $(tot_s + tot_q)* n= m_2 * [tot_s * t + tot_q * (t-1)]$

    ------提取公因式

    $n = m_2 * [tot_s * t + tot_q * (t-1)]/ (tot_s + tot_q)$

    ------nn 系数化 11

    所以这种情况的公式我们也推出来了，所以这个题我们就做完了QwQ 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;
}

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

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

    感谢你的观看QwQ QwQ~

    • 1

    [NOIP 2009 普及组] 细胞分裂

    信息

    ID
    71
    时间
    1000ms
    内存
    125MiB
    难度
    4
    标签
    递交数
    3
    已通过
    2
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 72ms