codeforces 922F Divisibility 构造

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

$\text{[math]}$ Let's define $\text{[math]}$ for some set of integers $\text{[math]}$ as the number of pairs a, b in $\text{[math]}$ , such that:

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

You are to find such a set $\text{[math]}$ , which is a subset of {1, 2, ..., n} (the set that contains all positive integers not greater than n), that $\text{[math]}$ .

Input

The only line contains two integers n and k $\text{[math]}$ .

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 $\text{[math]}$ you have found, in the second line print m integers — the elements of the set $\text{[math]}$ , in any order.

If there are multiple answers, print any of them.

Examples

input

3 3

output

No

input

6 6

output

Yes
5
1 2 4 5 6

input

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, $\text{[math]}$ .

In the third example, the valid pairs in the output set are (2, 4), (4, 8), (2, 8). Thus, $\text{[math]}$

题意：I 是一个正整数集合，I中取两个数a,b( a > b )使得a%b==0 的(a,b)组数定义为 f(I)

给定N，K，问是否存在f(I)=K，并且 I 中的元素小于等于N的集合 I ，若有，输出任意方案

题解：构造，cf的独特题目类型，变化太多了。直接说（抄来的）题解吧：

第一步：

先让 I 包含从1到m的所有数，使此时的 f(I) 恰好大于等于K

(恰好的含义是：若 I 包含从1到m-1的所有数，f(i)<K)

找到这样的m。

如何找？可以用筛法求出 b 与比它小的数组成的合法数对个数，记为val[b]，然后求val的累加和，找到临界点，就能找到m。

第二步：

考虑从当前集合中删除一些数。

只考虑删除素数（删除合数计算贡献太麻烦）

素数b对当前答案的贡献是m/b。

越大的素数对当前答案的贡献越小，所以可以考虑从小到大删除素数，维护当前答案。

至于为什么删除素数就可以……不会证明。

细节可以见代码

 1 /*
 2 Welcome Hacking
 3 Wish You High Rating
 4 */
 5 #include<iostream>
 6 #include<cstdio>
 7 #include<cstring>
 8 #include<ctime>
 9 #include<cstdlib>
10 #include<algorithm>
11 #include<cmath>
12 #include<string>
13 using namespace std;
14 int read(){
15     int xx=0,ff=1;char ch=getchar();
16     while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
17     while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
18     return xx*ff;
19 }
20 const int maxn=300005;
21 int N,K,val[maxn],prime[30000],cnt,limit,ans;
22 bool del[maxn];
23 void pre(){
24     for(int i=2;i<=N;i++){
25         if(!val[i])
26             prime[++cnt]=i;
27         val[i]++;
28         for(int j=i+i;j<=N;j+=i)
29             val[j]++;
30     }
31 }
32 int main(){
33     //freopen("in","r",stdin);
34     N=read(),K=read();
35     pre();
36     long long tot=0;
37     for(int i=1;i<=N;i++){
38         tot+=val[i];
39         if(tot>=K){
40             ans=limit=i;
41             break;
42         }
43     }
44     if(tot>K)
45         for(int i=1;i<=cnt;i++){
46             if(tot==K)
47                 break;
48             if(tot-K>=limit/prime[i]){
49                 del[prime[i]]=1;
50                 tot-=limit/prime[i];
51                 ans--;
52             }
53         }
54     if(tot!=K)
55         printf("No
");
56     else{
57         printf("Yes
");
58         printf("%d
",ans);
59         for(int i=1;i<=limit;i++)
60             if(!del[i])
61                 printf("%d ",i);
62         puts("");
63     }
64     return 0;
65 }

View Code