問題一覧 > 通常問題

No.2211 Frequency Table of GCD

レベル : / AI推定難易度 : 1375 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 143
作問者 : Shirotsume / テスター : 👑 qand ygussany
お気に入りにしたユーザー ProblemId : 8931 / 自分の提出
問題文最終更新日: 2023-02-10 21:18:43
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 376 (順位表) の他の問題:

Problem Statement

You are given an integer sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$, where each element is between $1$ and $M$, inclusive. For each of $k=1, 2, \dots, M$, solve the following problem.

  • Find the number, modulo $998244353$, of subsequences of $A$ (not necessarily contiguous) of length at least $1$ such that the greatest common divisor of all elements of the subsequence is $k$.

Here, even if two subsequences are the same as sequences, they are counted as different subsequences if the positions they are taken from differ.

Constraints

  • All input values are integers.
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq M \leq 2 \times 10^5$
  • $1 \leq A_i \leq M$

Input

The input is given from Standard Input in the following format.

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

Output

Output over $M$ lines. On the $i$-th line, output the answer for $k = i$.

Sample

Sample 1
Input
3 4
1 2 4
Output
4
2
0
1

For $A = (1, 2, 4)$, there are $4$ subsequences whose greatest common divisor is $1$: $(1), (1,2), (1,4), (1,2,4)$.

There are $2$ subsequences whose greatest common divisor is $2$: $(2), (2,4)$.

There are no subsequences whose greatest common divisor is $3$.

There is $1$ subsequence whose greatest common divisor is $4$: $(4)$.

Sample 2
Input
10 10
3 1 4 1 5 9 2 6 5 3
Output
999
5
13
1
3
1
0
0
1
0

The maximum value of $A$ does not necessarily equal $M$.

Sample 3
Input
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
Output
83885254
360709868

Output the remainder when divided by $998244353$.

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