問題一覧 > 通常問題

No.2211 Frequency Table of GCD

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 131
作問者 : ShirotsumeShirotsume / テスター : 遭難者遭難者 👑 ygussanyygussany
3 ProblemId : 8931 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-02-10 21:18:43

問題文

長さが $N$ で、各要素が $1$ 以上 $M$ 以下である整数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます。$k=1, 2, \dots, M$ のそれぞれについて、以下の問題を解いてください。

  • $A$ の連続とは限らない長さ $1$ 以上の部分列であって、部分列の要素すべての最大公約数が $k$ になるものの個数を $998244353$ で割った余りを求めてください。

ただし、部分列は列として同じであっても、取り出す位置が異なれば異なる部分列として数えます。

制約

  • 入力は全て整数
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq M \leq 2 \times 10^5$
  • $1 \leq A_i \leq M$

入力

入力は標準入力から以下の形式で与えられる。

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$

出力

$M$ 行にわたって出力せよ。 $i$ 行目には、 $k = i$ のときの答えを出力せよ。

サンプル

サンプル1
入力
3 4
1 2 4
出力
4
2
0
1

$A = (1, 2, 4)$ について、最大公約数が $1$ の部分列は $(1), (1,2), (1,4), (1,2,4)$ の $4$ つです。

最大公約数が $2$ の部分列は $(2), (2,4)$ の $2$ つです。

最大公約数が $3$ の部分列はありません。

最大公約数が $4$ の部分列は $(4)$ の $1$ つです。

サンプル2
入力
10 10
3 1 4 1 5 9 2 6 5 3
出力
999
5
13
1
3
1
0
0
1
0

$A$ の最大値が $M$ と一致するとは限りません。

サンプル3
入力
40 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1
出力
83885254
360709868

$998244353$ で割った余りを出力してください。

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