Codeforces 922.F Divisibility

Imp is really pleased that you helped him. But it you solve the last problem, his gladness would raise even more.

image Let's define image for some set of integers image

as the number of pairs a, b in

image

, such that:

• a is strictly less than b;
• a divides b without a remainder.

You are to find such a set image

, which is a subset of {1, 2, ..., n} (the set that contains all positive integers not greater than n), that

image

.

Input

The only line contains two integers n and k

image

.

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

image

you have found, in the second line print m integers — the elements of the set

image

, 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, image

.

In the third example, the valid pairs in the output set are (2, 4), (4, 8), (2, 8). Thus, image

.

题目大意：在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;
}

或者可以删除质数，但都有一个问题，证明可以被删去的数能组合出需要的和