$ 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