AtCoderBeginnerContest169復習＆まとめ（後半） - Qiita

AtCoder ABC169 2020-05-31(日)に行われたAtCoderBeginnerContest169の問題をA問題から順に考察も踏まえてまとめたものとなります． 後半ではDEの問題を扱います．前半はこちら． 問題は引用して記載していますが，詳しくはコンテストページの方で確認してください． コンテストページはこちら 公式解説PDF D問題 Div Game 問題文 正の整数$N$が与えられます。$N$に対して、以下の操作を繰り返し行うことを考えます。 ・はじめに、以下の条件を全て満たす正の整数$z$を選ぶ。 ◦ある素数$p$と正の整数$e$を用いて、$z=p^e$と表せる ◦$N$が$z$で割り切れる ◦以前の操作で選んだどの整数とも異なる ・$N$を、$N/z$に置き換える 最大で何回操作を行うことができるか求めてください。 とりあえず素因数分解すれば，この問題は簡単に解け