問題リンク
問題概要
正整数Nが与えられる、2以上N以下の整数Kを選んで次の操作を行う。
- NがKで割り切れるならば、NをN/Kで置き換える。
- 割り切れなければ、NをN-Kで置き換える。
- NがK未満になったら終了する。
最終的なNの値が1になるKはいくつあるか。
制約：\(2 \leqq N \leqq 10^{12}\)
解法
Kの条件を式で表すと、
\(N = (aK+1)K^b\)
となる非負整数a,bが存在することと同値である。
Nが最大\(10^{12}\)と大きいため、愚直に全探索するのは難しいが、
Kが\(\sqrt{N}\)より大きい時、NはKで2回以上割れない、したがってbは2以上にはならないことを利用する。
(\(\sqrt{N}\)を境目として探索方法や遷移式を変えるテクニックはたまに使う。問題 問題(ネタバレ注意))
今回の場合は\(K \geqq \sqrt{N}\)とすると\(b=0,1\)なので
\(N = aK+1\)
もしくは
\(N=(aK+1)K=aK^2+K\)
となる、後者は\(K^2 \geqq N\)より\(a=0\)、よって\(N=K\)となる。
前者の場合は\(K=(N-1)/a\)となるので、候補はN-1の約数のみとなる。
このなかで\(\sqrt{N}\)より大きいものを全て列挙すれば良い。
あとは\(\sqrt{N}\)より小さいものに関して愚直に全探索すれば答えが得られる。
(追記：\(b > 0\)の時はKがNの約数なので、Nの約数について調べるだけでよい、という方法で解いている人が多いみたいです。解説もそうしています)
提出
https://atcoder.jp/contests/abc161/submissions/11523694
感想
自己最高順位。
