P8909 [RC-06] Multiples

Given $n$ and an array $a$ of length $n$, where $a_1 \sim a_n$ are all positive integers, and each $a_i$ is generated uniformly at random in $[1,10^9]$. For each $0 \le k \le n$, compute how many positive integers $x$ in $[1,m]$ are multiples of exactly $k$ values among $a_i$ (that is, there exist exactly $k$ indices $1 \le i \le n$ such that $a_i \mid x$).

The first line contains two positive integers $n, m$. The next line contains $n$ positive integers $a_1 \sim a_n$.

Output one line with $n+1$ integers. The $i$-th integer is the answer for $k=i-1$.

There are no partial scores in this problem. You only get points if you get AC. All testdata satisfy: $1 \le n \le 2500$, $1 \le m \le 10^9$, $1 \le a_i \le 10^9$, and each $a_i$ is generated uniformly at random in $[1,10^9]$. **In this problem, $6$ test cases satisfy $n=2500$, and $2$ test cases satisfy $n \le 10$, for a total of $8$ test cases.** **All testdata are generated in the following way: run the following pseudocode exactly once, and use its output as your input.** ``` function rnd(int l,int r): return a random integer in [l,r] function main(): input n,m for this test case output n,m output n positive integers, each is the return value of rnd(1,10^9) ``` If you do not understand the generation method above, you can also read the corresponding C++ code: ```cpp #include using namespace std; typedef long long ll; int main(){ freopen("in.txt","w",stdout); int n,m; cin>>n>>m; cout