問題一覧 > 通常問題

No.2128 Round up!!

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 : 遭難者 / テスター : 👑 AngrySadEight 👑 potato167
1 ProblemId : 8772 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-16 12:24:35

問題文

正整数 X,A,BX,A,B が与えられます。
変数 xx があり、はじめ x=Xx=X を満たしています。
あなたは以下の 22 つの操作を好きな順番で 00 回以上好きな回数だけ行うことができます :

  • xx を xx 以上の最小の AA の倍数に置き換える。
  • xx を xx 以上の最小の BB の倍数に置き換える。

    • あなたが操作を終了した時点での xx の値としてあり得るものは何通りあるでしょうか？ 998244353998244353 で割った余りを求めてください。
    TT 個のテストケースが与えられるので、それぞれについて答えを求めてください。

    制約

  • 1≤T≤5×1041\le T\le 5\times 10^4
  • 1≤X,A,B≤10181\le X,A,B\le 10^{18}
  • 入力は全て整数である。

    • 入力

    TT
case1\text{case}_1
case2\text{case}_2
⋮\vdots
caseT\text{case}_T
    各テストケースは以下の形式で与えられる : 
    XX AA BB

    出力

    TT 行出力してください。
    ii 行目 (1≤i≤T)(1\le i\le T) には、 casei\text{case}_i に対する答えを出力してください。

    サンプル

    サンプル1
    入力
    3
1 2 3
4 1 5
90441586 5486714 5123786
    出力
    5
2
5123755

    11 つ目の操作を操作 AA 、22 つ目の操作を操作 BB と呼びます。
    11 つ目のテストケースでは 1,2,3,4,61,2,3,4,6 の 55 つの整数を作ることができます。以下はそれらの整数を作る操作の一例です :

  • 操作を行わない。最終的に x=1x=1 となる。
  • 操作 AA を行う。最終的に x=2x=2 となる。
  • 操作 AA をした後に操作 BB を行う。最終的に x=3x=3 となる。
  • 操作 BB をした後に操作 AA を行う。最終的に x=4x=4 となる。
  • 操作 BB をした後に操作 AA を行い、操作 BB を行う。最終的に x=6x=6 となる。

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