問題一覧 > 通常問題

No.2211 Frequency Table of GCD

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

問題文

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

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

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

制約

  • 入力は全て整数
  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 1≤Ai≤M1 \leq A_i \leq M

入力

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

NN MM
A1A_1 A2A_2 …\dots ANA_N

出力

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

サンプル

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

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

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

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

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

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

AA の最大値が MM と一致するとは限りません。

サンプル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

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

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