[AtCoder] ABC 169 D – Div Game

問題

方針

任意の素数 \( p\) について \( N \bmod p^m = 0\) となるような最大の正の整数 \( m \) が求められたとします。この素数 \( p\) に関して、操作回数を最大化するには、\( c = 1, 2, 3, \cdots \) と選べば良いので、

\[ \dfrac{n(n+1)}{2} \leq m\]

と満たす最大の \( n \) が操作回数となります。このような \(n\) は二分探索によって求めることができます。\( m \) の求め方は、\( \sqrt{N} \) までの範囲で探索すれば十分です。

コード