問題一覧 > 通常問題

No.2128 Round up!!

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

問題文

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

  • $x$ を $x$ 以上の最小の $A$ の倍数に置き換える。
  • $x$ を $x$ 以上の最小の $B$ の倍数に置き換える。

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

    制約

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

    • 入力

    $T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$
    各テストケースは以下の形式で与えられる : 
    $X$ $A$ $B$

    出力

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

    サンプル

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

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

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

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