問題一覧 > 通常問題

No.2128 Round up!!

レベル : / AI推定難易度 : 2450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 46
作問者 : 👑 qand / テスター : 👑 AngrySadEight 👑 potato167
お気に入りにしたユーザー ProblemId : 8772 / 自分の提出
問題文最終更新日: 2022-11-16 12:24:35
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 368 (順位表) の他の問題:

Problem Statement

You are given positive integers $X,A,B$.
There is a variable $x$, which initially satisfies $x=X$.
You can perform the following $2$ operations in any order, any number of times, $0$ or more:

  • Replace $x$ with the smallest multiple of $A$ that is greater than or equal to $x$.
  • Replace $x$ with the smallest multiple of $B$ that is greater than or equal to $x$.

    • How many values are possible for $x$ at the point when you finish performing operations? Find the count modulo $998244353$.
    You are given $T$ test cases; find the answer for each of them.

    Constraints

  • $1\le T\le 5\times 10^4$
  • $1\le X,A,B\le 10^{18}$
  • All inputs are integers.

    • Input

    $T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$
    Each test case is given in the following format: 
    $X$ $A$ $B$

    Output

    Print $T$ lines.
    On the $i$-th line $(1\le i\le T)$, print the answer for $\text{case}_i$.

    Sample

    Sample 1
    Input
    3
1 2 3
4 1 5
90441586 5486714 5123786
    Output
    5
2
5123755

    We call operation number $1$ operation $A$, and operation number $2$ operation $B$.
    In test case number $1$, the $5$ integers $1,2,3,4,6$ can be obtained. The following are examples of operations that produce these integers:

  • Perform no operations. Finally, $x=1$.
  • Perform operation $A$. Finally, $x=2$.
  • Perform operation $A$, then operation $B$. Finally, $x=3$.
  • Perform operation $B$, then operation $A$. Finally, $x=4$.
  • Perform operation $B$, then operation $A$, then operation $B$. Finally, $x=6$.

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