Edit

【pythonでABC169を解説】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()

プログラミング

-Edit
-