{"problem":{"name":"[RC-06] Multiples","description":{"content":"给出 $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$）。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8909"},"statements":[{"statement_type":"Markdown","content":"给出 $n$，以及一个长度为 $n$ 的数组 $a$，$a_1\\sim a_n$ 都是正整数，且 $a_i$ 在 $[1,10^9]$ 均匀随机生成。\n\n对每个 $0\\le k\\le n$ 计算 $[1,m]$ 中有几个正整数 $x$ 恰好是 $k$ 个 $a_i$ 的倍数（也就是恰好存在 $k$ 个 $1\\le i\\le n$，$a_i\\mid x$）。\n\n## Input\n\n第一行两个正整数 $n,m$。\n\n接下来一行 $n$ 个正整数 $a_1\\sim a_n$。\n\n## Output\n\n输出一行 $n+1$ 个整数，第 $i$ 个是 $k=i-1$ 的答案。\n\n[samples]\n\n## Note\n\n本题没有部分分，只有 AC 才能得分。\n\n所有数据均满足：$1\\le n\\le 2500$，$1\\le m\\le 10^9$，$1\\le a_i\\le 10^9$，且 $a_i$ 在 $[1,10^9]$ 中均匀随机生成。\n\n**本题有 $6$ 组数据满足 $n=2500$，$2$ 组数据满足 $n\\le 10$，共 $8$ 组数据。**\n\n**所有数据都是如下方式生成：运行以下伪代码恰好一次生成，将其输出作为你的输入。**\n\n```\nfunction rnd(int l,int r):\n\nreturn [l,r] 之内的随机整数\n\nfunction main():\n\n输入本组数据的 n,m\n输出 n,m\n输出 n 个正整数，都是 rnd(1,10^9) 的返回值\n```\n\n如果你不理解上面的生成方式，也可以阅读对应的 C++ 代码：\n\n```cpp\n#include<bits/stdc++.h>\nusing namespace std;\ntypedef long long ll;\nint main(){\n\tfreopen(\"in.txt\",\"w\",stdout);\n\tint n,m;\n\tcin>>n>>m;\n\tcout<<n<<' '<<m<<'\\n';\n\tmt19937_64 rng(time(0));\n\tconst int M=1e9;\n\tfor(int i=1;i<=n;i++)cout<<rng()%M+1<<' ';\n}\n```\n\n样例不满足 $a_i$ 在 $[1,10^9]$ 均匀随机生成，因此样例不是合法的输入数据。测试数据中不包含样例。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8909","tags":["O2优化"],"sample_group":[["5 1000000\n1 2 3 4 5","0 266666 333335 266665 116668 16666"]],"created_at":"2026-03-03 11:09:25"}}