難問と言われた12/3(土） 21:00- のAt Coder ABC280 のD問題を解説します。

問題は、
「与えられた整数Nに対し、K!がNの倍数となる最小のKを求めよ」
というもの。

階乗とは、例えばK=5のとき、
5 x 4 x 3 x 2 x 1
となるものです。

当然ですが、Kをカウントアップさせたループで、階乗を計算してNの倍数か否かを判定していては、時間が足りません。

カンのいい人は、Nを素因数分解すればよいのではと気づくでしょう。
やってみましょう。

N=30の場合

N = 30 = 2 x 3 x 5
となります。

なんと、素因数分解したすべての約数がK=5の階乗　(5 x 4 x 3 x 2 x 1)に含まれています。

答えは、当然5となりますね。

N=60の場合

それでは、 N = 60のときはどうでしょう。
素因数分解すると、
N = 2 x 2 x 3 x 5
となります。

この場合、K=5の階乗と比較してみると、
(5 x 4 x 3 x 2 x 1 ) / (2 x 2 x 3 x 5)
= (4 x 1) / (2 )
となり、残った数は、分子（階乗側）が4, 分母（素数側）が2となりました。
4は2の倍数のため、割り切る事が出来、やはり答えは5となります。

N=120の場合

N = 120の場合も、
(5 x 4 x 3 x 2 x 1) / (2 x 2 x 2 x 3 x 5)
= (4 x 1 ) / (2 x 2)
となり、割り切れるので、やはり答えは5ですね。

N=240の場合

それでは、N=240の場合は、というと、
N = 2 x 2 x 2 x 2 x 3 x 5
となり、
(5 x 4 x 3 x 2 x 1) / (2 x 2 x 2 x 3 x 5)
= (4 x 1 ) / (2 x 2 x 2)
= 1 /(2)
で、5の階乗では、Nで割り切れない事がわかります。

それでは、5の次に大きい数は、というと6であり、
(6 x 5 x 4 x 3 x 2 x 1 ) / (2 x 2 x 2 x 3 x 5)
= 6 x (5 x 4 x 3 x 2 x 1 ) / (2 x 2 x 2 x 3 x 5)
= 6 / (2 x 3)
となり、6 = 2 x 3 なので、
6の階乗がNで割り切れる最小の数となります。

これを踏まえた上で、一般化して解いてみましょう。

一般化した解法

まず、素因数分解した結果をリスト化します。
prime_list = [p1, p2, p3, .....]

やりたい事は、このリストと、Kの階乗の数字リストとのマッチングですが、
Kが10^9の場合、リストの数が大きすぎて扱えなくなってしまいます。

Kの階乗をすべて管理するのではなく、
「重複のない、N以下の数で、素因数分解したリストの倍数が含まれるもの」
を管理すればよいわけです。

これを管理するためには、重複を管理するリストを使います。

仮に、これをfact_list=[p1,p2,p3,....]などとすると、
prime_listのリストにある素数すべてについて、
１．階乗リストにない数であれば、階乗リストに登録して、素数リストからは削除
２．階乗リストにある数であれば、p x 2, p x 3,....と増やしていき、リストにない数になったら、登録して、素数リストからは削除
２－１．増やしていった数がp x qだった場合、qが素数リストの残りの数の倍数であるかを確認
２－２．倍数であったら、その数を素数リストから削除して、次の要素をチェック
３．階乗リストの中の一番大きい数が答え
とすればよいことになります。

N=240 の場合の解法例

N=240について行ってみましょう。
prime_list = [2,2,2,2,3,5]
fact_list=[]
からはじまります。
１回目のループでは、
p = prime_list[0]
で、この場合、p=2となります。
この数は、fact_listにはないため、fact_listに2を登録します。
そして、prime_listからは削除します。
この操作を行った後、
prime_list = [2,2,2,3,5]
fact_list=[2]
となります。

２回目のループでは、
p=2となりますが、fact_listに2が存在するため、2倍します。
q = 2として、
P2 = p x q = 2 x 2 = 4
この数は、fact_listに存在しないため、fact_listに4を登録します。
そして、pをprime_listから削除します。
このとき、q=2が残りのリスト prime_list=[2,2,3,5]の中で、2の倍数として存在するため、prime_listから更に2を削除します。
このとき、
prime_list = [2,3,5]
fact_list = [2, 4]
となります。

３回目のループでは、
p=2となります。fact_listに2が存在するため、2倍します。
q = 2 とすると、
p2 = p x q = 2 x 2 = 4
となりますが、この数もfact_listに存在するため、qをカウントアップします。
q = 3 とすると、
p2 = p x q = 2 x 3 = 6
となり、この数がfact_listに存在しないため、登録して、pをprime_listから削除します。
そして、q=3が、残りのリストprime_list=[3,5]の中で3の倍数として存在するため、prime_listから更に3を削除します。
このとき、
prime_list=[5]
fact_list = [2,4,6]
となります。

４回目のループでは、
p=5となります。fact_listに5が存在しないため、登録して、pをprime_listから削除します。
最終的に、
prime_list=[]
fact_list=[2,4,6,5]
となったため、答えは、K=max(fact_list) = 6となります。

Pythonで書いてみよう

ロジックがわかれば、後は実装するだけです。
素数リストの長さが動的に変わるため、forループではなく、whileループを使います。

Python

N=240
prime_list = [2,2,2,2,3,5]
prime_list.sort()
fact_list=[]
iteration_count=0
while 1:
    if prime_list == []: #リストがなくなったらループ終了
        break
    iteration_count+=1
    print(iteration_count,"th Loop.prime_list=",prime_list,"fact_list=",fact_list)
    p = prime_list.pop(0)
    q = 1
    p2 = p
    print("#1.   p=",p)
    while 1:
        if p2 not in fact_list: #fact_listに値が存在しなければ、登録して終了
            print("#2.   p2=",p2," q=",q)
            fact_list.append(p2)
            break
        #p2がfact_listに存在しないため、qをカウントアップ
        p2 += p
        q += 1
    #qが残りのリストの倍数であるかを確認
    print("#2-1. q=",q,"prime_list=",prime_list,"fact_list=",fact_list)
    for pw in (prime_list[:]): #動的に変わるため、prime_list[:]でコピー
        if pw > q: # pwがqより大きければ、qが以降のpwの倍数になることはない。
            break
        if q % pw == 0: #qがpwの倍数であった場合
            prime_list.remove(pw)
            q /= pw #qをpwで割って、更にリストの他の要素の倍数かを調べる
            print("#2-2. pw=",pw,"removed. next q=",q,"prime_list=",prime_list)
print("#3.   fact_list=",fact_list,"max_num=",max(fact_list))
print("answer K=", max(fact_list))

console

1 th Loop.prime_list= [2, 2, 2, 2, 3, 5] fact_list= []
#1.   p= 2
#2.   p2= 2  q= 1
#2-1. q= 1 prime_list= [2, 2, 2, 3, 5] fact_list= [2]
2 th Loop.prime_list= [2, 2, 2, 3, 5] fact_list= [2]
#1.   p= 2
#2.   p2= 4  q= 2
#2-1. q= 2 prime_list= [2, 2, 3, 5] fact_list= [2, 4]
#2-2. pw= 2 removed. next q= 1.0 prime_list= [2, 3, 5]
3 th Loop.prime_list= [2, 3, 5] fact_list= [2, 4]
#1.   p= 2
#2.   p2= 6  q= 3
#2-1. q= 3 prime_list= [3, 5] fact_list= [2, 4, 6]
#2-2. pw= 3 removed. next q= 1.0 prime_list= [5]
4 th Loop.prime_list= [5] fact_list= [2, 4, 6]
#1.   p= 5
#2.   p2= 5  q= 1
#2-1. q= 1 prime_list= [] fact_list= [2, 4, 6, 5]
#3.   fact_list= [2, 4, 6, 5] max_num= 6
answer K= 6

素因数分解（参考）

参考程度に、素因数分解の部分も書いておきます。

Python

N=240
Nw = N
prime_list=[]
for k in range(2,int(N**(1/2))+1): #Nの平方根までカウントアップ
    if k > Nw:
        break
    while 1: #おなじ数で割り切れなくなるまで割り続ける
        if Nw % k == 0:
            Nw /= k
            Nw = int(Nw)
            prime_list.append(k)
        else:
            break
if Nw > 1: #残った数を加える
    prime_list.append(Nw)
print(prime_list)
# [2, 2, 2, 2, 3, 5]