難問と言われた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ループを使います。
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))
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
素因数分解（参考）
参考程度に、素因数分解の部分も書いておきます。
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]