P8909 [RC-06] Multiples

给出 $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$ 的答案。

本题没有部分分，只有 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++ 代码： ```cpp #include using namespace std; typedef long long ll; int main(){ freopen("in.txt","w",stdout); int n,m; cin>>n>>m; cout