Problem Description

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$).

Input Format

The first line contains two positive integers $n, m$.

The next line contains $n$ positive integers $a_1 \sim a_n$.

Output Format

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

5 1000000
1 2 3 4 5

0 266666 333335 266665 116668 16666

Hint

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:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	freopen("in.txt","w",stdout);
	int n,m;
	cin>>n>>m;
	cout<<n<<' '<<m<<'\n';
	mt19937_64 rng(time(0));
	const int M=1e9;
	for(int i=1;i<=n;i++)cout<<rng()%M+1<<' ';
}

The sample does not satisfy that $a_i$ is generated uniformly at random in $[1,10^9]$, so the sample is not valid input data. The testdata do not include the sample.

Translated by ChatGPT 5