求階乘?

藍(lán)橋杯2022省賽題目

問(wèn)題描述

滿足?N?! 的末尾恰好有?K?個(gè) 0 的最小的?N?是多少?

如果這樣的?N?不存在輸出??1?。

輸入格式

一個(gè)整數(shù)?K?。

輸出格式

一個(gè)整數(shù)代表答案。

樣例輸入

2

樣例輸出

10

評(píng)測(cè)用例規(guī)模與約定

對(duì)于?30%?的數(shù)據(jù), 1≤K≤10^6.

對(duì)于?100%?的數(shù)據(jù), 1≤K≤10^18.

思路：?

題目大意：求滿足N!的末尾恰好有K個(gè)0的最小的N，如果這樣的N不存在，返回-1

解法一：暴力法

????????遍歷1~10^18（題目中100%的數(shù)據(jù)規(guī)模）內(nèi)所有數(shù)，對(duì)每個(gè)數(shù)求階乘，再計(jì)算末尾0的個(gè)數(shù)，最后判斷是否為K個(gè)0，很明顯是超時(shí)了（看下面代碼分析）。但可以得到部分的分?jǐn)?shù)，沒(méi)有時(shí)間的話可以這樣簡(jiǎn)單處理。

? ? ? ? 代碼分析：這個(gè)是計(jì)算末尾0的個(gè)數(shù)的代碼，很明顯在這個(gè)環(huán)節(jié)就沒(méi)辦法達(dá)到100%數(shù)據(jù)的要求，因?yàn)?≤K≤10^18，而這個(gè)代碼復(fù)雜度是O(n),要計(jì)算10^18次，但藍(lán)橋杯計(jì)算量一般不超過(guò)10^8，所以用暴力法計(jì)算是超時(shí)的。?

res = 0     # 統(tǒng)計(jì)末尾0的個(gè)數(shù)
while m % 10 == 0:
    res+=1
    m//10    # 去掉最后一位

解法二：?

解題關(guān)鍵：給出一個(gè)N，如何快速計(jì)算它的階乘中末尾0的個(gè)數(shù)?

• 思考1：什么樣的數(shù)，相乘后能夠產(chǎn)生0?

10=2*5

20=2*2*5
7200=72*2*5*2*5
我們可以發(fā)現(xiàn)每個(gè)數(shù)字末尾的每個(gè)0都可以看成是2和5相乘得到
所以我們可以對(duì)題目中樣例進(jìn)行分析：10!=1 * 2 * 3 * 4 * 5* 6 * 7 * 8 * 9 * 10，我們發(fā)現(xiàn)10！內(nèi)有一對(duì)現(xiàn)成的2和5，但樣例輸出是2，說(shuō)明還有一對(duì)2和5，沒(méi)錯(cuò)，只要把10進(jìn)行分解成2*5就可以再得到一對(duì)，這樣兩對(duì)2和5說(shuō)明10的階乘末尾有2個(gè)零。

結(jié)論：給定一個(gè)數(shù)的階乘，計(jì)算它的因子中2*5出現(xiàn)的次數(shù)，即可確定末尾0的個(gè)數(shù)?

• 思考:2：找2*5的數(shù)目，因子2是否需要尋找?

不需要。通過(guò)10!=1 * 2 * 3 * 4 * 5* 6 * 7 * 8 * 9 * 10可以發(fā)現(xiàn)，因子5只有在5和10中才有。但因子2在2,4,6,8,10中都存在，出現(xiàn)2多5少的現(xiàn)象，所以只需要找到稀有的因子5即可，因?yàn)橐蜃?是肯定有剩余的。

問(wèn)題轉(zhuǎn)換：

求N的階乘尾部0的個(gè)數(shù)? ?? ?求N的階乘中因子5的個(gè)數(shù)
????????對(duì)階乘中的因子5進(jìn)行分析，1 2 3 4 5…10 …15…20…25…30…35… 50…55… 75…100…105…125…，可以發(fā)現(xiàn)當(dāng)?shù)?4時(shí)，前面每隔5都會(huì)都會(huì)有一對(duì)2和5，共有4對(duì)。但在25時(shí)會(huì)出兩個(gè)5（兩對(duì)2和5），總共就有6對(duì)，如果你輸入5的話，沒(méi)有末尾為5個(gè)0的階乘，則返回-1。在124之前每隔25會(huì)出兩對(duì)，但125會(huì)出三對(duì)。把前面出現(xiàn)的5加起來(lái)總共有31個(gè)，但這樣很麻煩，有沒(méi)有更容易操作的方法呢？看看下面的操作：

?????????為什么是這樣算呢？是因?yàn)槲覀兿劝押幸粋€(gè)及以上5的25個(gè)數(shù)全部取出一個(gè)5加到總數(shù)num，那么本來(lái)一個(gè)5的數(shù)就變成0個(gè)（可以忽略），本來(lái)兩個(gè)5的數(shù)變成一個(gè)5的數(shù)，本來(lái)3個(gè)5的變成二個(gè)5的。再這樣對(duì)原本含有二個(gè)及以上5的5個(gè)數(shù)（現(xiàn)在是含有一個(gè)及以上5的數(shù)）操作一次，只剩下一個(gè)含5的數(shù)，最后再對(duì)含5的1個(gè)數(shù)取出一個(gè)5加到總數(shù)num，這樣就把全部的因子5轉(zhuǎn)移到了總數(shù)num。

結(jié)論：求N的階乘中因子5的個(gè)數(shù),將N每次除以5的商求和即可。

定義求一個(gè)整數(shù)階乘末尾0的個(gè)數(shù)的函數(shù)：

def cal_zero(N):
    res = 0   # 統(tǒng)計(jì)0的個(gè)數(shù)
    while N:
        N //= 5
        res += N
    return res

復(fù)雜度：每一次變成原來(lái)的五分之一，所以復(fù)雜度為,是logN級(jí)別的，計(jì)算10^18的數(shù)只需要算26次即可，非常高效！

注意：題目中 1≤K≤10^18的K是指整數(shù)階乘末尾0的個(gè)數(shù)的范圍，不是整數(shù)的范圍，說(shuō)明整數(shù)范圍可能更大，我們以10^19的整數(shù)試一下，看看階乘末尾0的個(gè)數(shù)能不能大于10^18。

def cal_zero(N):
    res = 0  # 統(tǒng)計(jì)0的個(gè)數(shù)
    while N:
        N //= 5
        res += N
    return res

N = 1e19
print(cal_zero(N))  # 2.5e+18

????????很顯然，10^19的整數(shù)階乘末尾有2.5e+18個(gè)0，大于題目100%數(shù)據(jù)大小，是滿足要求的。所以N可以取10^19來(lái)計(jì)算。

????????上面只是求出了整數(shù)階乘末尾0的個(gè)數(shù)，還需要找出滿足末尾K個(gè)0的最小整數(shù)，下面用二分法來(lái)求解。

二分法登場(chǎng)啦！

使用條件：更小的N對(duì)應(yīng)的是小的尾0個(gè)數(shù)，更大的N對(duì)應(yīng)的是大的0個(gè)數(shù)，所以末尾0的個(gè)數(shù)是一個(gè)遞增的有序數(shù)列，可以用二分法來(lái)求解。
定義一個(gè)check()函數(shù)：將所有從1到N的階乘分成尾部0個(gè)數(shù)<k的左半部分和>=k的右半部分，二分結(jié)束后檢查R位置（因?yàn)镽是滿足≥check()的最小值）的尾部0個(gè)數(shù)是否為k即可，若不是即返回-1。

def check(k):
    L,R=1,int(1e19)    
    while L+1!=R:
        mid = (L+R)//2
        if cal_zero(mid)>=k:    
            R = mid
        else:
            L=mid
    if cal_zero(R)==k:  # cal_zero(r)：滿足階乘末尾0≥k的最小整數(shù)
      return R
    else:               # 沒(méi)有階乘末尾k個(gè)0的整數(shù)
      return -1   

?二分法的復(fù)雜度也是O(logN)，所以算法復(fù)雜度為文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-411613.html

代碼演示：?

k=int(input())
def cal_zero(N):
    res = 0   # 統(tǒng)計(jì)末尾0的個(gè)數(shù)
    while N:
        N //= 5
        res += N
    return res
def check(k):
    L,R=1,int(1e19)    
    while L+1!=R:
        mid = (L+R)//2
        if cal_zero(mid)>=k:    
            R = mid
        else:
            L=mid
    if cal_zero(R)==k:  # cal_zero(r)：滿足階乘末尾0≥k的最小整數(shù)
      return R
    else:               # 沒(méi)有階乘末尾k個(gè)0的整數(shù)
      return -1   
print(check(k))

到了這里，關(guān)于藍(lán)橋杯刷題014——求階乘（二分法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！