At Coder ABC280 D問題 (Factorial & Multiply) を解説

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

https://atcoder.jp/contests/abc280/tasks/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: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: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]
```