ABC161 F - Division or Subtraction (600)
$ Nが最終的に1になる$ Kの条件は以下のどちらか
$ N \equiv 1 (\mod K)
$ Nが$ Kの倍数の場合、$ Kの倍数で無くなるまで$ Kで割った後、$ N \equiv 1 (\mod K)
単純に実装すると$ O(N \log N)だが、実際には$ \sqrt{N}まで見れば$ \frac{N}{K}も計算できるので$ O(\sqrt{N} \ log N)になる
$ K = \sqrt{N}の時、$ Kと$ \frac{N}{K}を二重にカウントしないように注意