AOJ 2707 Jail

概要

問題文

自然数 0,1,2,\ldots に対して以下の操作を  N-1 回行ったときの先頭の数字を答えよ。

  • 先頭から 0,k,2k,\ldots 番目の数字を削除する。

制約: 1 \leq N \leq 10^5, 2 \leq k \leq 10^5

解法

下のように、ある数字が削除される前は先頭から何番目だったか逆から構成していくと分かりやすい。

削除前 012k-1kk+1k+2
削除後 01k-2k-1k

これを見るとK-1個おきに削除前の数字と対応が付いているのがわかる。 削除後の x 番目の数字は削除前だと  K * \lfloor \frac{x}{K-1} \rfloor + x \bmod (K-1) + 1 番目となることがわかるので これを N-1 回繰り返し計算すれば良い。