Imp is really pleased that you helped him. But it you solve the last problem, his gladness would raise even more.
as the number of pairs a, b in
, such that:
- a is strictly less than b;
- a divides b without a remainder.
, which is a subset of {1, 2, ..., n} (the set that contains all positive integers not greater than n), that
.
Input
The only line contains two integers n and k
.
Output
If there is no answer, print "No".
Otherwise, in the first line print "Yes", in the second — an integer m that denotes the size of the set
you have found, in the second line print m integers — the elements of the set
, in any order.
If there are multiple answers, print any of them.
Examples
input
Copy
3 3
output
No
input
Copy
6 6
output
Yes
5
1 2 4 5 6
input
Copy
8 3
output
Yes
4
2 4 5 8
Note
In the second sample, the valid pairs in the output set are (1, 2), (1, 4), (1, 5), (1, 6), (2, 4), (2, 6). Thus,
.
In the third example, the valid pairs in the output set are (2, 4), (4, 8), (2, 8). Thus,
.
题目大意：在1~n中选任意个数组成一个集合I,定义f(I) = I中的每个数被I中的其它的多少个数整除的和.已知f(I) = k,求I.
思路：首先找到一个n使得集合1~n恰好满足f(i) >= k;
然后直接按照每个数的贡献用堆进行降序排序，逐次删除（标记）直至满足条件，因为最后一项的增加所减少的贡献不多于n/2，所以从n/2+1处开始遍历（入队），然后从小于等于需要被减去的最大数开始减去
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,k,sum[300010],d[300010],cur,leftt,vis[300010],ans;
priority_queue <pair<int,int> >q;
int main()
{
scanf("%d%d",&n,&k);
for (int i = 1; i <= n; i++) //遍历 是i的倍数则++
for (int j = i * 2; j <= n; j += i)
d[j]++;
for (int i = 1; i <= n; i++) //找到cur刚好大于
{
sum[i] = sum[i - 1] + d[i];
if (sum[i] >= k)
{
leftt = sum[i] - k; //需要减去的
cur = i; //记录下
break;
}
}
if (!cur)
puts("No");
else
{
puts("Yes");
if (leftt == 0) //恰好
{
printf("%d\n",cur);
for (int i = 1; i <= cur; i++)
printf("%d ",i);
}
else
{
for (int i = cur / 2 + 1; i <= cur; i++)
q.push(make_pair(d[i],i)); //从cur/2+1入队（降序）
while (leftt)
{
pair <int,int> temp = q.top();
q.pop();
if (leftt >= temp.first) //一直减去能减去的最大值，直到leftt==0
{
leftt -= temp.first;
vis[temp.second] = 1;//标记该下标
}
}
for (int i = 1; i <= cur; i++)
if (!vis[i])
ans++;
printf("%d\n",ans);
for (int i = 1; i <= cur; i++)
if (!vis[i])
printf("%d ",i);
}
}
return 0;
}
或者可以删除质数，但都有一个问题，证明可以被删去的数能组合出需要的和
