No.2132 1 or X Game
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 56
作問者 :
nok0
/ テスター :
ぷら
taiga0629kyopro
タグ : / 解いたユーザー数 56
作問者 :
nok0
/ テスター :
ぷら
taiga0629kyopro
問題文最終更新日: 2022-11-22 20:28:02
問題文
以下のゲームをゲーム $n$ と呼びます。
Alice と Bob でゲームをします。はじめ $n$ 個の石があります。
Alice から始めて、交互に次の操作のうちどちらか一方を選択して行い、操作を行えなくなった方が負けとなります。
- 石を $1$ 個取り除く。
- 石を $X$ 個取り除く。この操作を選択した次の自分の番にはこの操作は選択できない。
ゲーム $1$、ゲーム $2$、…、ゲーム $N$ のうち、二人が最適に行動したとき Alice が勝つゲームは何個あるか求めてください。
答えはあまり大きくはならず、64 bit 整数型に収まりますが、折角なので $998244353$ で割ったあまりを出力してください。
一つの入力ファイルにつき、 $T$ 個のテストケースに答えてください。
制約
- 入力は全て整数
- $1 \le T\le 2\times 10^5$
- $1 \le N,X \le 10^{18} $
入力
入力は以下の形式で標準入力から与えられる。$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各テストケースは以下の形式で与えられる。
$N$ $X$
出力
$T$ 行出力せよ。
$i$ $(1\leq i \leq T)$ 行目には、$i$ 番目のテストケースの答えを $998244353$ で割ったあまりを出力せよ。
サンプル
サンプル1
入力
3 4 3 1 1 10000000000 99999999
出力
2 1 8778235
$1$ 番目のテストケースでは、ゲーム $1$ とゲーム $3$ で Alice が勝ちます。ゲーム $1$ では最初に石を $1$ 個取り除き、ゲーム $3$ では最初に石を $3$ 個取り除けばよいです。
$3$ 番目のテストケースでは、答えは $5000000000$ ですが、それを $998244353$ で割ったあまりを出力することに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。