問題一覧 > 通常問題

No.2896 Monotonic Prime Factors

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 67
作問者 : loop0919loop0919 / テスター : hiro1729hiro1729
2 ProblemId : 11361 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-09-12 18:35:18

問題文

正整数 $n, m$ に対して $f(n, m)$ を、次の条件をすべて満たす長さ $n$ の整数列 $a = (a_1, a_2, \cdots, a_n)$ の個数と定義します。

  • $2 \le a_i$
  • $\displaystyle \prod_{i = 1}^n a_i = m$
  • $1 \le i < j \le N$ ならば、 $a_i$ の任意の素因数 $p$ と $a_j$ の任意の素因数 $q$ について $p \le q$ を満たす。

また正整数 $x$ があり、はじめ $x = 1$ です。
次のように説明されるクエリが $Q$ 個与えられるので、$k = 1, 2, \cdots, Q$ の順に処理してください。

  • $x$ を $x \times A_k$ に更新する。その後、$f(B_k, x)$ を $998244353$ で割った余りを出力する。

    • 素因数とは

    $2$ 以上の整数 $n$ の素因数とは、次の条件をすべて満たす集合 $P = \{P_1, P_2, \cdots, P_{|P|}\}$ の要素を指します。

    • $P_i$ は素数である。
    • $i \ne j$ ならば $P_i \ne P_j$ である。
    • 次の条件を満たす長さ $|P|$ の整数列 $E = (E_1, E_2, \cdots, E_{|P|})$ が存在する。
      • $1 \le E_i$
      • $\displaystyle \prod_{i = 1}^{|P|} P_i^{E_i} = n$

    ここで、このような $P$ は一意に定まることが証明できます。

    $\prod$（総積記号）とは

    長さ $n ~ (1 \le n)$ の数列 $a = (a_1, a_2, \cdots, a_n)$ について $\displaystyle \prod_{i = 1}^n a_i$ とは、$a_1 \times a_2 \times \cdots \times a_n$ を指します。

    入力

    $Q$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_Q$ $B_Q$

    入力はすべて以下の制約を満たす。

    • $1 \le Q \le 10^5$
    • $2 \le A_k \le 10^5$
    • $1 \le B_k \le 10^5$
    • 入力はすべて整数である。

    出力

    $Q$ 行出力せよ。 $k$ 行目には $k$ 個目のクエリの答えを出力せよ。

    サンプル

    サンプル1
    入力
    3
12 2
15 3
7 7
    出力
    2
6
0

    各クエリについて、次のことが言えます。

    • $1$ 個目のクエリについて、
      • $x$ を $1 \times 12 = 12$ に更新する。
      • その後、 $f(2, 12)$ を計算する。条件を満たす整数列は $(2, 6), (4, 3)$ の $2$ 個である。理由は以下の通りである。
        • $(2, 6)$ について、$2 = 2, ~ 6 = 2 \times 3$ である。すべての要素が $2$ 以上かつ総積が $12$ であり、かつ $2 \le 2, ~ 2 \le 3$ であるため条件を満たす。
        • $(4, 3)$ について、$4 = 2^2, ~ 3 = 3$ である。すべての要素が $2$ 以上かつ総積が $12$ であり、かつ $2 \le 3$ であるため条件を満たす。
    • $2$ 個目のクエリについて、
      • $x$ を $12 \times 15 = 180$ に更新する。
      • その後、 $f(3, 180)$ を計算する。条件を満たす整数列は $(2,2, 45), (2, 6, 15), (2, 18, 5), (4, 3, 15), (4, 9, 5), (12, 3, 5)$ の $6$ 個である。
    • $3$ 個目のクエリついて、
      • $x$ を $180 \times 7 = 1260$ に更新する。
      • その後、$f(7, 1260)$ を計算する。条件を満たす整数列は存在しないため、 $0$ 個である。
    サンプル2
    入力
    16
10 1
3465 13
121 4
2450 1
4620 3
2310 2
40425 7
245 13
11550 13
98 15
16940 3
20 13
9091 5
49 20
33 28
84 31415
    出力
    1
0
56
1
171
24
593775
354817320
916064377
951522724
1128
32537773
270725
913512504
802620790
0

    各クエリの答えとして、$998244353$ で割った余りを出力することを忘れないでください。

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