ABC 169 「D - Div Game」を見直す

D - Div Game

問題文はちょっと長いので「AtCoder」のサイトを見てもらうのがいいと思います。

D - Div Game

こう思った

これは整数Nは何種類の「素数を累乗した数」からできているかを求める問題や。

例えば、24であれば、素因数は「2,2,2,3」なので、「2^1,2^2,3^1 = 2,4,3」の３パターン、32であれば、素因数は「2,2,2,2,2,」なので、「2^1,2^2, = 2,4」の２パターンとなる（もう一つ2^2が作れるが同じ数なのでパターンは増えない）。

解答

でここでメインとなるのが素因数分解をどうやるかだけど、自分で書かずに以下「Qiita」の投稿を参照したので、せめて解説をコメントをつけて理解を深めておこうと思う。

Pythonで高速素因数分解〜競プロ用〜 - Qiita

作成したコードは以下

def factorization(n):
   arr = []
   for i in range(2, int(-(-n**0.5//1))+1):
       if n%i == 0:
           cnt=0
           while n%i == 0:
               cnt += 1
               n //= i
           arr.append([i, cnt])

   if n != 1:
       arr.append([n, 1])

   return arr
N = int(input())
ans = 0
if N != 1:
   fact_list = factorization(N)
   for _, i in fact_list:
       j = 1
       while i >= j:
           ans += 1
           i = i - j
           j += 1
           
print(ans)

公式の解説コードともそう変わらない内容だったように思える。私なりの解説を加えてみたのが以下、これで素因数分解のアルゴリズムへの理解が深まっているといいなと思う。

#2以上の整数n => [[素因数, 指数], ...]の2次元リストを取得
def factorization(n):
   #素因数とその数を保存するためのアレイ（辞書でもいい）
   arr = []
   """
   ルートNの２乗はNなので確認するのは、n^1/2（ルートN）まででOK
   このループの回し方だと4とか6素数以外も検証してしまうが、
   上記理由により計算量は問題ないかつ、
   検証する数の素数は既に検証済みなので素数としてカウントされ得ない
   """
   for i in range(2, int(-(-n**0.5//1))+1):
       #割り切れる場合はiの値が素因数なので割り切れなくなるまで割る
       if n%i == 0:
           cnt=0
           while n%i == 0:
               cnt += 1
               n //= i
           #割り切れなくなった段階でWhileループを抜け記録
           arr.append([i, cnt])
   #n自体が素数であった場合にこちらで追加
   if n != 1:
       arr.append([n, 1])
   return arr

N = int(input())
ans = 0
#1の場合は0を表示する
if N != 1:
   fact_list = factorization(N)
   #今回素因数は関係ないので無視
   for _, i in fact_list:
       j = 1
       """
       iから「1,2,3,4,....」１ずつ短調増加する数列を引いていき
       第何項まで引けるかを全ての素因数に対し実行
       （やってることは単純なのに説明がむずいな）
       """"
       while i >= j:
           ans += 1
           i = i - j
           j += 1
           
print(ans)