题目描述

给出 $n$，以及一个长度为 $n$ 的数组 $a$，$a_1\sim a_n$ 都是正整数，且 $a_i$ 在 $[1,10^9]$ 均匀随机生成。

对每个 $0\le k\le n$ 计算 $[1,m]$ 中有几个正整数 $x$ 恰好是 $k$ 个 $a_i$ 的倍数（也就是恰好存在 $k$ 个 $1\le i\le n$，$a_i\mid x$）。

输入格式

第一行两个正整数 $n,m$。

接下来一行 $n$ 个正整数 $a_1\sim a_n$。

输出格式

输出一行 $n+1$ 个整数，第 $i$ 个是 $k=i-1$ 的答案。

5 1000000
1 2 3 4 5

0 266666 333335 266665 116668 16666

提示

本题没有部分分，只有 AC 才能得分。

所有数据均满足：$1\le n\le 2500$，$1\le m\le 10^9$，$1\le a_i\le 10^9$，且 $a_i$ 在 $[1,10^9]$ 中均匀随机生成。

本题有 $6$ 组数据满足 $n=2500$，$2$ 组数据满足 $n\le 10$，共 $8$ 组数据。

所有数据都是如下方式生成：运行以下伪代码恰好一次生成，将其输出作为你的输入。

function rnd(int l,int r):

return [l,r] 之内的随机整数

function main():

输入本组数据的 n,m
输出 n,m
输出 n 个正整数，都是 rnd(1,10^9) 的返回值

如果你不理解上面的生成方式，也可以阅读对应的 C++ 代码：

#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<<' ';
}

样例不满足 $a_i$ 在 $[1,10^9]$ 均匀随机生成，因此样例不是合法的输入数据。测试数据中不包含样例。