正经题解｜A33698.因子

A33698.因子

本题先对于每一个 $a_i$ 求出因子的个数，然后存到一个数组里面，再对数组排序。最后对于排好序的数组贪心的从大到小选择元素即可。

#include <bits/stdc++.h>
using namespace std;

int n, m, a[200010], cnt[200010];

int get(int x){
	set<int>s;
	for(int i = 1; i * i <= x; i ++ ){
		if(x % i == 0) {
			s.insert(i);
			s.insert(x / i);
		}
	}
	return (int)s.size();
}

int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i ++ ){
		cin >> a[i];
		cnt[i] = get(a[i]);
	}
	sort(cnt + 1, cnt + 1 + n);
	int sum = 0, ans = 0;
	for(int i = n; i >= 1; i -- ){
		sum += cnt[i];
		ans ++;
		if(sum >= m){
			break;
		}
	}
	cout << ans << endl;
    return 0;
}