ABC169 D - Div Game

問題原文

atcoder.jp

解法

の 因数であれば当然割り切れるので、素因数分解をしておきたい気持ちになる。

一度使った は二度使えないので、 を因数として持つ場合には、 と使っていきたくなる。

実装

from collections import Counter
N = int(input())
 
def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table
 
 
T = prime_factorization(N)
C = Counter(T)
 
ans = 0
for v in C.values():
    nx = 1
    while v >= nx:
        v -= nx
        ans += 1
        nx += 1
 
print(ans)

感想

Cが沼だったので泣きながら逃げてきた。
解きやすい問題でよかった（茶diffなのは納得いかないけど）