AtCoder Beginner Contest 161 F - Division or Substraction

解法

「 $N$ が $K$ で割り切れる時」「割り切れない時」で操作の種類が変わるので、 $N$ を $K$ で割った余りに注目してみましょう。

もし $N$ を $K$ で割った余りが $0$ でない場合には、 $N$ は $K$ 未満になるまで $N-K$ に置き換えられ続けます。つまり、この余りはずっと変わりません。よって $N$ を割り切れないような $K$ のうち条件を満たすものは、その余りが $1$ であるもの全てです。

このような $K$ の個数を求めましょう。余りが $1$ であるということは正整数 $a$ を用いて $N = aK+1$ と表現できるということです（ $N \ge 2$ なので $a \le 0$ はあり得ません）。これを変形して $K=\frac{N-1}{a}$ となり、このような正整数 $a$ が存在する $K$ は $N-1$ の約数なので、その個数を数えれば良いです。ただし $K=1$ は除きます。

一方 $N$ が $K$ で割り切れる時には、割り切れなくなるまで $K$ で割られ、その後は上記と同じ流れになります。よって $N$ の約数（ $1$ を除く）であるような $K$ を全て試し、 $N$ を割り切れなくなるまで割ってから、さらに割ろうとした時の余りが $1$ であるかを調べれば良いです。約数は多く見積もっても $2\sqrt{N}$ 個以下（実際はもっと少ないです）なので、全て調べても間に合います。