問題一覧 > 通常問題

No.1923 Divisor Array

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 6
作問者 : ebi_flyebi_fly
1 ProblemId : 8083 / 自分の提出
問題文最終更新日: 2022-05-01 23:50:22

問題文

正整数 $N,M,K$ が与えられます。$D$ を小さい方から $K$ 個の素数の積とします。 以下の条件を満たす長さ $N+1$ の数列 $A = (A_0, A_1, \dots, A_N)$ はいくつありますか?答えを $998244353$ で割った余りを出力してください。

条件

  • $A_0 = D$
  • $i = 1,\dots,N$ について、$A_i$ は $\displaystyle\prod_{j = 0}^{i-1}A_j$ の正の約数である。
  • $\displaystyle\prod_{i = 1}^{N}A_i$ の正の約数の個数は $M$ 以下である。

入力

$N$ $M$ $K$
  • $1 \leq N \leq 10^9$
  • $1 \leq M \leq 2000$
  • $1 \leq K \leq 10^9$
  • 入力に含まれる値は全て整数である

出力

答えを $998244353$ で割った余りを出力せよ。

サンプル

サンプル1
入力
2 2 2
出力
5

$K=2$ であるので $D=2\times3$ です。このとき、条件を満たす長さ $3$ の数列 $A$ は次の $5$ つです。

  • $(A_0,A_1,A_2) = (6,1,1)$
  • $(A_0,A_1,A_2) = (6,1,2)$
  • $(A_0,A_1,A_2) = (6,2,1)$
  • $(A_0,A_1,A_2) = (6,1,3)$
  • $(A_0,A_1,A_2) = (6,3,1)$
サンプル2
入力
3 3 4
出力
25
サンプル3
入力
1000000000 2000 1000000000
出力
362056892

$998244353$ で割った余りを出力することに注意してください。


出典 CPCTF22

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