No.2211 Frequency Table of GCD
タグ : / 解いたユーザー数 143
作問者 :
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もしくは右上の雲マークをクリックしてアカウントを作成してください。