自动搬运

查看原文

来自洛谷，原作者为

	yeshubo_qwq 我是 luxu。

搬运于2025-08-24 22:43:39，当前版本为作者最后更新于2022-12-24 22:21:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

首先考虑最简单的暴力。

对于每个数 $x$，枚举它的倍数 $j$，并给 $a_j$ 增加 $1$。

统计 $a_j>0$ 的数中满足 $a_j=k$ 的数量，减一减就是 $a_j=0$ 的数量。

在随机数据下跑的飞快。

注意到数据的确是随机的，交一发，AC 了！

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
//#define int long long
using namespace std;
using namespace __gnu_pbds;
int n,m,i,x,j,ans[2505];
gp_hash_table <int,int> a;
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for (i=1;i<=n;i++){
		cin>>x;
		for (j=x;j<=m;j+=x) a[j]++;
	}
	int tot=m;
	for (gp_hash_table <int,int>::iterator it=a.begin();it!=a.end();it++)
		ans[it->second]++,tot--;
	cout<<tot<<' ';
	for (i=1;i<=n;i++) cout<<ans[i]<<' ';
	return 0;
}