F. Divisibility

Codeforces
IDCF922F
Time1000ms
Memory256MB
Difficulty
constructive algorithmsdpgreedynumber theory
English · Original
Chinese · Translation
Formal · Original
Imp is really pleased that you helped him. But it you solve the last problem, his gladness would raise even more. <center>![image](https://espresso.codeforces.com/07971ee6e5e75115459520faadc129b3f0e828cc.png)</center>Let's define for some set of integers as the number of pairs _a_, _b_ in , such that: * _a_ is **strictly less** than _b_; * _a_ **divides** _b_ without a remainder. You are to find such a set , 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. [samples] ## 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, .
Imp 对你帮助他感到非常高兴。但如果你能解决最后一个问题,他的喜悦还会进一步提升。 你需要找到一个集合,它是 #cf_span[{1, 2, ..., n}] 的子集(即包含所有不超过 #cf_span[n] 的正整数的集合),使得其交错和等于 #cf_span[k]。 输入仅包含一行,包含两个整数 #cf_span[n] 和 #cf_span[k]。 如果无解,请输出 "_No_"。 否则,在第一行输出 "_Yes_",第二行输出一个整数 #cf_span[m],表示你找到的集合的大小;在第三行输出 #cf_span[m] 个整数——即该集合的元素,顺序任意。 如果存在多个答案,输出任意一个即可。 在第二个样例中,输出集合中的合法数对为 #cf_span[(1, 2)], #cf_span[(1, 4)], #cf_span[(1, 5)], #cf_span[(1, 6)], #cf_span[(2, 4)], #cf_span[(2, 6)]。因此,交错和为 #cf_span[k]。 在第三个样例中,输出集合中的合法数对为 #cf_span[(2, 4)], #cf_span[(4, 8)], #cf_span[(2, 8)]。因此,交错和为 #cf_span[k]。 ## Input 输入仅包含一行,包含两个整数 #cf_span[n] 和 #cf_span[k]。 ## Output 如果无解,请输出 "_No_"。否则,在第一行输出 "_Yes_",第二行输出一个整数 #cf_span[m],表示你找到的集合的大小;在第三行输出 #cf_span[m] 个整数——即该集合的元素,顺序任意。如果存在多个答案,输出任意一个即可。 [samples] ## Note 在第二个样例中,输出集合中的合法数对为 #cf_span[(1, 2)], #cf_span[(1, 4)], #cf_span[(1, 5)], #cf_span[(1, 6)], #cf_span[(2, 4)], #cf_span[(2, 6)]。因此,交错和为 #cf_span[k]。 在第三个样例中,输出集合中的合法数对为 #cf_span[(2, 4)], #cf_span[(4, 8)], #cf_span[(2, 8)]。因此,交错和为 #cf_span[k]。
**Definitions** Let $ n, k \in \mathbb{Z}^+ $. Let $ S \subseteq \{1, 2, \dots, n\} $ be a subset. Define $ P(S) = \left| \left\{ (a,b) \in S \times S \mid a < b \text{ and } a \mid b \right\} \right| $. **Constraints** $ 1 \leq n \leq 10^5 $, $ 0 \leq k \leq \binom{n}{2} $ **Objective** Find a subset $ S \subseteq \{1, 2, \dots, n\} $ such that $ P(S) = k $. If no such $ S $ exists, output "_No_". Otherwise, output "_Yes_", followed by $ |S| $ and the elements of $ S $.
Samples
Input #1
3 3
Output #1
No
Input #2
6 6
Output #2
Yes
5
1 2 4 5 6
Input #3
8 3
Output #3
Yes
4
2 4 5 8
API Response (JSON)
{
  "problem": {
    "name": "F. Divisibility",
    "description": {
      "content": "Imp is really pleased that you helped him. But it you solve the last problem, his gladness would raise even more. <center>![image](https://espresso.codeforces.com/07971ee6e5e75115459520faadc129b3f0e8",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF922F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Imp is really pleased that you helped him. But it you solve the last problem, his gladness would raise even more.\n\n<center>![image](https://espresso.codeforces.com/07971ee6e5e75115459520faadc129b3f0e8...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Imp 对你帮助他感到非常高兴。但如果你能解决最后一个问题,他的喜悦还会进一步提升。\n\n你需要找到一个集合,它是 #cf_span[{1, 2, ..., n}] 的子集(即包含所有不超过 #cf_span[n] 的正整数的集合),使得其交错和等于 #cf_span[k]。\n\n输入仅包含一行,包含两个整数 #cf_span[n] 和 #cf_span[k]。\n\n如果无解,请输出 \"_No_\"。\n\n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $.  \nLet $ S \\subseteq \\{1, 2, \\dots, n\\} $ be a subset.  \nDefine $ P(S) = \\left| \\left\\{ (a,b) \\in S \\times S \\mid a < b \\text{ and } a \\mid b \\right\\} \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments