問題概要
問題ページ
-
D - Div Game
問題ページへ移動する
問題文
正の整数 \(N\) が与えられます。 \(N\) に対して、以下の操作を繰り返し行うことを考えます。
- はじめに、以下の条件を全て満たす正の整数 \(z\) を選ぶ。
- ある素数 \(p\) と正の整数 \(e\) を用いて、 \(z=p^e\) と表せる
- \(N\) が \(z\) で割り切れる
- 以前の操作で選んだどの整数とも異なる
- \(N\) を、\(N/z\) に置き換える
最大で何回操作を行うことができるか求めてください。
制約
- 入力はすべて整数である。
- \(1 \leq N \leq 10^{12}\)
問題の考察
ACコード
import sys
import collections
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
n = int(input().rstrip('\n'))
d = collections.defaultdict(int)
for i in range(2, int(n ** 0.5) + 1):
while n % i == 0:
d[i] += 1
n //= i
if n != 1:
d[n] += 1
cnt = 0
for k, v in d.items():
tc = 0
for i in range(1, v + 1):
tc += i
if tc <= v:
cnt += 1
else:
break
print(cnt)
if __name__ == '__main__':
solve()