ABC161 F - Division or Subtraction

解法

まず重要な点として、$N$が$K$で割り切れないときに、$N-K$が$K$で割り切れるということはありえない
$N$が$K$で割り切れるということは$gcd(N, K) = K$になるが
$gcd(N, K) = gcd(N-K, K)$であり、
$N-K$と$K$の最大公約数は操作前の値と等しくなる
よって、操作としては

1. Kで割り切れるだけ割る
2. Kで引けるだけ引く

という流れになる
2は結局$mod K$をとることに等しい

以上を踏まえて以下の2つのパターンが考えられる

1. KがNで割り切れるとき

このときはNをKで割れるだけ割る。割った値を$N'$とすると
$N' \mod K \equiv 1$となればよい
Nを割り切るKというのはNの約数なので、Nの約数を列挙して(1は除く)、以上をシミュレーションすればよい

2. KがNで割り切れないとき

$N \mod K \equiv 1$となればよい
こうなるような$K$の数を数えたい
元の式を式変形すると
$N - 1 \mod K \equiv 0$
$N-1$は$K$で割り切れる、つまり$K$は$N-1$の約数となる
N-1の約数の個数-1が答えになる

1と2で重複して数えられるものがないか気になるが、
$N$と$N-1$は互いに素なので、公約数は1しか存在せず、問題にならない

提出コード

https://atcoder.jp/contests/abc161/submissions/19722162