P8909 [RC-06] Multiples 题解

yeshubo_qwq · 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;
}