ABC 169 D - Div Game

問題

自然数 $n$ を、相異なる数で素数の冪乗になっているようなものの積で表すとき、最大で何個の積で表すことができるか。（$n \leq 10 ^ {12}$）

atcoder.jp

解説

$n = p _ {1} ^ {e _ 1} \cdots p _ {k} ^ {e _ k}$ と素因数分解すると、各素因数については独立に考えられるので、各 $i$ について $e _ i$ を何個の異なる数の和で表わせるかを求め、それらを合計すればよい。
$e _ i$ を異なる数の和で表わすには、引く数 $a$ を $1$ ずつ増やしていきながら、$0$ を下まわらない限り $a$ を引いていき、その回数を求めればよい。

実装

n = int(input())
if n == 1:
    print(0)
    exit()
F = {}
tmp = n
i = 2
while i**2 <= tmp:
    cnt = 0
    while tmp % i == 0:
        cnt += 1
        tmp //= i
    if cnt > 0:
        F[i] = cnt
    i += 1
if tmp != 1 or F == {}:
    F[tmp] = 1
ans = 0
for p in F:
    a = 1
    while F[p] >= a:
        F[p] -= a
        ans += 1
        a += 1
print(ans)

atcoder.jp