ABC161 F. Division or Substraction
問題
正の整数Nが与えられる。
2以上N以下の整数Kを決めて、NがK未満になるまで次の操作を繰り返す
- NがKで割り切れるならNをN/Kに置き換える。そうでないなら、NをN-Kに置き換える
最終的にNが1になるようなKはいくつあるか？
制約
- 2 <= N <= 10^12
解法
まず、「NがKで割り切れる」というのは、Nを割れる数＝Nの約数である。まず、これが割る場合のKの候補となる。
Nの約数dでNを割ったあと、それがまだdで割れるなら操作の条件から割り続ける必要がある。
なので、Nをdで割り切れるだけ割った後の値N'が最終的に1になるかを考えれば良い。
上記以外で、引き算をしてから割り算が発生するか？考える。
引き算してから割り算が発生する＝「X-KをしてからKの倍数になるか？」ということだが、これはXがKの倍数のときしかありえない(上の事例)ので、引き算をしてから割り算が発生することはない。
したがって、Nの約数以外は、引き算のみが行われると考えて良い。
最後に、あるKがあって、あるXが引き算操作のみで最終的に1になるか？を考える。
これは「X-Kを繰り返して最終的に1になるか？」であるが、引き算操作だけ考えればよいので、
1 -> 1+K -> 1+2K -> 1+3K -> 1+4K -> ...
となるKのみである。
言い換えると、
X = 1 + mK (m>0の整数)
の場合に最終的に1になるので、XはKで割ってあまりが1の場合＝「X mod K=1」であればよい。
割り算が発生するケースは、Nの約数について、割れるだけ割ったあとの値XがX mod K = 1を見れば良い。
割り算が発生しないケースは、X=Nの場合＝「N = 1 + mK」になる場合なので、K=(N-1)の約数が答えになる。
約数列挙と割れるだけ割る操作の部分の計算量がかかるが、約数列挙はO(sqrt(N))程度、割り切れるだけ割る操作は、約数の個数*O(logN)程度なので、十分高速に求められる。
