問題一覧 > 通常問題

No.1651 Removing Cards

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 66
作問者 : 👑 chocoruskchocorusk / テスター : 👑 hos.lyrichos.lyric
9 ProblemId : 2877 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-20 18:44:56

問題文

$1, 2, \ldots , N$ が書かれたカードが $1$ 枚ずつ左からこの順に一列に並んでいます。ラスク君は次の操作をカードが残り $1$ 枚になるまで繰り返します。

  1. 残っているカードのうち、左から $K x + 1$ 番目 ($x$ は非負整数) のカードすべてに印をつける。
  2. 印のついたカードをすべて取り除く。
最後に残るカードに書かれた数は何でしょうか。

$N$ の値が $N_1, N_2, \ldots, N_Q$ の場合それぞれについて答えを求めてください。

入力

$K\ Q$
$N_1$
$N_2$
$\vdots$
$N_Q$

  • $2\leq K\leq 10^4$
  • $1\leq Q\leq 10^5$
  • $1\leq N_i\leq 10^{18}$
  • 入力はすべて整数である。

出力

$Q$ 行出力してください。$i$ 行目 ($1\leq i\leq Q$) には、$N=N_i$ の場合に、操作を繰り返し行ったとき最後に残るカードに書かれた数を出力してください。

サンプル

サンプル1
入力
3 1
7
出力
5

  • はじめ、カードに書かれた数は左から順に $1, 2, 3, 4, 5, 6, 7$ です。
  • $1$ 回目の操作では、左から $1, 4, 7$ 番目のカードが取り除かれます。残ったカードに書かれた数は左から順に $2, 3, 5, 6$ です。
  • $2$ 回目の操作では、左から $1, 4$ 番目のカードが取り除かれます。残ったカードに書かれた数は左から順に $3, 5$ です。
  • $3$ 回目の操作では、左から $1$ 番目のカードが取り除かれます。残ったカードに書かれた数は $5$ です。

サンプル2
入力
5 3
3
34
334
出力
3
30
290

サンプル3
入力
3141 5
9265358979
3238462643
3832795028
8419716939
9375105820
出力
9263828525
3238177188
3832261774
8417162552
9373616394

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。