AtCoder Beginner Contest 169 D - Div Game【Python】
https://atcoder.jp/contests/abc169/tasks/abc169_d
AtCoder ProblemsでDifficulty: 732、Solve Probability: 34%でした。
素因数分解を行い各指数について答えを求めていきました。
1, 2, 3...の累積和[0, 1, 3, 6...]を求め二分探索で各指数が何回操作を行えるかを求めるというややこしいことをしてしまいましたが、
解説を見たところ、シンプルに各指数から1,2,3...を引けるまで引いていきその回数を答えに加算すれば良かったようです。
import bisect # https://algo-method.com/descriptions/119 # 素因数分解 # 460 = 2^2 x 5 x 23 の場合 # 返り値は [(2, 2), (5, 1), (23, 1)] def prime_factorize(N): # 答えを表す可変長配列 res = [] # √N まで試し割っていく for p in range(2, N): # p * p <= N の範囲でよい if p * p > N: break # N が p で割り切れないならばスキップ if N % p != 0: continue # N の素因数 p に対する指数を求める e = 0 while N % p == 0: # 指数を 1 増やす e += 1 # N を p で割る N //= p # 答えに追加 res.append((p, e)) # 素数が最後に残ることがありうる if N != 1: res.append((N, 1)) return res N = int(input()) a = [i for i in range(1, 50)] sum_a = [0] for i in range(1, 50): sum_a.append(sum_a[i-1] + a[i-1]) pf = prime_factorize(N) ans = 0 for p, e in pf: ans += bisect.bisect_right(sum_a, e) - 1 print(ans)