巧妙的构造算法：特定整除二元组的最短序列
题目大意
给定一个数字 k（1 \leq k \leq 10^5），要求构造一个长度为 n 的序列 a_1, a_2, \dots, a_n，使得恰好存在 k 个二元组 (i, j) 满足 i < j 且 a_i \mid a_j（即 a_i 整除 a_j）。核心要求：最小化序列长度 n。
思路陷阱
初学者很容易想到使用 2 的幂次方（如 1, 2, 4, 8, \dots）。因为幂次方序列中，任意前面的数都能整除后面的数。但由于 2^{20} > 10^6，2 的幂最多只能用到 2^{19}。长度为 20 的序列最多只能产生 \binom{20}{2} = 190 对。如果为了达到 k = 10^5 对而去无脑追加数字，序列长度会达到几千万，直接 MLE 或违反长度限制，并且由于远离最短长度限制而失分。
破局点：题目并未要求序列元素互不相同！
数学最优解法 (The "1 and 2s" Strategy)
1. 基础块：全等序列
如果我们在序列中放入 x 个完全相同的数字（例如全是 2），那么它们两两之间必然满足 a_i \mid a_j（因为 2 \mid 2）。因此，长度为 x 的全等序列，恰好能提供 \binom{x}{2} = \frac{x(x-1)}{2} 对有效二元组。
2. 精准调参：插入 1
对于任意 k，我们可以先找到一个最大的 x，使得：
此时，距离目标对数还差一个余数：r = k - \frac{x(x-1)}{2}。显然 0 \leq r < x。
如何零代价地恰好补齐这 r 对？答案是在全等序列中插入一个 1。1 可以整除任何数。如果我们在序列中放入一个 1，且保证它的右边恰好有 r 个 2，那么这个 1 就会与它右边的所有 2 结合，精准地产生额外 r 对。
3. 最终构造方案
- 序列元素组成：1 个
1，以及 x 个2。 - 排列方式：先放置 (x - r) 个
2，然后放置1，最后放置 r 个2。 - 特判：如果 r = 0，则不需要放
1，直接输出 x 个2即可。
此时，序列的长度为 x 或 x + 1。由于 \binom{n}{2} \geq k \Rightarrow n \approx \sqrt{2k}，理论上任何序列要产生 k 对，其长度至少也要达到 \Theta(\sqrt{k})。因此，我们的构造方法达到了数学上的绝对最小长度，可以拿下满分。
C++ 满分代码实现
Gimini 版：
#include <iostream>
#include <cmath>
using namespace std;
int main() {
// 优化输入输出流
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long m;
if (!(cin >> m)) return 0;
// 特判 m = 0 的情况，直接输出长度至少为 2 的不整除序列
if (m == 0) {
cout << 2 << "\n";
cout << 2 << " " << 3 << "\n";
return 0;
}
// 1. 寻找最大的 k，使得 k*(k-1)/2 <= m
// 使用求根公式近似估算，再微调，避免浮点数精度或二分耗时
long long k = (long long)(sqrt(2.0 * m));
while (k * (k - 1) / 2 > m) {
k--;
}
while ((k + 1) * k / 2 <= m) {
k++;
}
// 2. 计算差值 R
long long R = m - k * (k - 1) / 2;
// 3. 构造并输出序列
if (R == 0) {
// 如果恰好匹配，输出 k 个 2
cout << k << "\n";
for (int i = 0; i < k; i++) {
cout << 2 << (i == k - 1 ? "" : " ");
}
cout << "\n";
} else {
// 如果有余数，长度为 k + 1
cout << k + 1 << "\n";
// 输出 (k - R) 个 2
for (int i = 0; i < k - R; i++) {
cout << 2 << " ";
}
// 输出 1 充当调节器
cout << 1 << " ";
// 输出 R 个 2，它们会被 1 整除
for (int i = 0; i < R; i++) {
cout << 2 << (i == R - 1 ? "" : " ");
}
cout << "\n";
}
return 0;
}
//qwen版本
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
long long k;
cin >> k;
// 找到最大的 x 使得 x*(x-1)/2 <= k
long long x = (long long)((1 + sqrt(1 + 8 * k)) / 2);
while (x * (x - 1) / 2 > k) x--;
while ((x + 1) * x / 2 <= k) x++;
long long pairs_from_twos = x * (x - 1) / 2;
long long r = k - pairs_from_twos; // 0 <= r < x
vector<int> ans;
if (r == 0) {
// 直接输出 x 个 2
for (int i = 0; i < x; i++) ans.push_back(2);
} else {
// 先放 (x - r) 个 2
for (int i = 0; i < x - r; i++) ans.push_back(2);
// 放 1
ans.push_back(1);
// 再放 r 个 2
for (int i = 0; i < r; i++) ans.push_back(2);
}
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++) {
if (i > 0) cout << " ";
cout << ans[i];
}
cout << endl;
return 0;
}