問題一覧 > 通常問題

No.2132 1 or X Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 56
作問者 : nok0 / テスター : ぷら taiga0629kyopro
1 ProblemId : 8769 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-22 20:28:02

問題文

以下のゲームをゲーム nn と呼びます。

Alice と Bob でゲームをします。はじめ nn 個の石があります。

Alice から始めて、交互に次の操作のうちどちらか一方を選択して行い、操作を行えなくなった方が負けとなります。

  • 石を 11 個取り除く。
  • 石を XX 個取り除く。この操作を選択した次の自分の番にはこの操作は選択できない。

ゲーム 11、ゲーム 22、…、ゲーム NN のうち、二人が最適に行動したとき Alice が勝つゲームは何個あるか求めてください。

答えはあまり大きくはならず、64 bit 整数型に収まりますが、折角なので 998244353998244353 で割ったあまりを出力してください。

一つの入力ファイルにつき、 TT 個のテストケースに答えてください。

制約

  • 入力は全て整数
  • 1≤T≤2×1051 \le T\le 2\times 10^5
  • 1≤N,X≤10181 \le N,X \le 10^{18}

入力

入力は以下の形式で標準入力から与えられる。 
TT
case1\mathrm{case}_1
case2\mathrm{case}_2
⋮\vdots
caseT\mathrm{case}_T
各テストケースは以下の形式で与えられる。 
NN XX

出力

TT 行出力せよ。

ii (1≤i≤T)(1\leq i \leq T) 行目には、ii 番目のテストケースの答えを 998244353998244353 で割ったあまりを出力せよ。

サンプル

サンプル1
入力
3
4 3
1 1
10000000000 99999999
出力
2
1
8778235

11 番目のテストケースでは、ゲーム 11 とゲーム 33 で Alice が勝ちます。ゲーム 11 では最初に石を 11 個取り除き、ゲーム 33 では最初に石を 33 個取り除けばよいです。

33 番目のテストケースでは、答えは 50000000005000000000 ですが、それを 998244353998244353 で割ったあまりを出力することに注意してください。

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