問題一覧 > 通常問題

No.2132 1 or X Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 50
作問者 : nok0nok0 / テスター : taiga0629kyoprotaiga0629kyopro ぷらぷら
1 ProblemId : 8769 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。