AtCoder Beginner Contest 169 [ D - Div Game ]をPythonで解く(400点、🟫茶diff)
問題
解法
整数Nを素因数分解する。
公式のpdfより引用。
N = p1e1 × ... × pkek と素因数分解されるとします。このとき、各 pi に対して、 z = pi1, pi2, ... と順番に選んでいくのが最適です。
素因数分解は、検索すればやり方はすぐわかるのだが、答えを出すロジックがかなり悩む。
他の人の書いたコードに良いのがあって、それを拝借。
pの1乗、2乗と素因数分解の結果から引いていく。
普通に素因数分解した値をNから割るのか?と思ってたけど、素因数分解がそもそも割り算した結果だから、素因数分解の結果から答えを数えて出すやり方がスマートですね。
実装
参考
ansを出すロジックを拝借。