题意
给定一个整数 \(x\)，定义一个操作：
选择一个 \(x\) 的因数 \(d\)，把 \(x\) 修改为 \(x-d\)。
限制相同的 \(d\) 值不能选择超过 \(2\) 次，需要在最多 \(1000\) 次操作内把 \(x\) 操作至 \(1\)，求操作序列。
（\(1 \le x \le 10^9\)）。
题解
为便于表达，下文中设 \(n\) 为待操作的数字。
发现 \(2\) 的正幂次数可以在相同的因子最多选择 \(1\) 次的情况下操作至 \(1\)，操作方法如下：
\[2^x \xrightarrow{2^{x - 1}} 2^{x - 1} \xrightarrow{2^{x - 2}} 2^{x - 2} \cdots 2 \xrightarrow{1} 1
\]
即对于 \(n = 2^x\)，选择因子 \(2^{x - 1}\)。
下面考虑 \(n\) 不为正幂次数的情况，考虑将 \(n\) 表达为 \(b \cdot 2^x\)，其中 \(b\) 为奇数，\(x\) 为非负整数。
考虑选择因子 \(2^x\)，那么 \(n\) 变为 \(\left(b - 1\right) \cdot 2^x\)，此时 \(b - 1\) 为偶数，可以将因子 \(2\) 提出，使其变为 \(n = \dfrac{b - 1}{2^y} 2^{x + y}\)，其中 \(2^y = \operatorname{lowbit}(b - 1)\)。，可以发现因为 \(b\) 为奇数，所以有 \(y \ge 1\)，在下次操作时选择的因子一定大于 \(2^x\)，所以在 \(b\) 消为 \(1\) 之前，每个因子最多选择一次。\(b\) 消为 \(1\) 之后使用上文介绍的适用于 \(2\) 的正幂次数的操作即可。
综上，我们可以在 \(\mathcal{O}(log n)\) 次数内将 \(n\) 操作至 \(1\)。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
int main() {
valueType T;
std::cin >> T;
for (int testcase = 0; testcase < T; ++testcase) {
valueType N;
std::cin >> N;
valueType x = 0, y = 0, K = 1;
while (N % 2 == 0) {
++x;
K *= 2;
N /= 2;
}
ValueVector result;
while (N > 1) {
result.push_back(K);
N -= 1;
while (N % 2 == 0) {
++x;
K *= 2;
N /= 2;
}
}
while (x > 0) {
result.push_back(K / 2);
K /= 2;
x -= 1;
}
ValueVector ans;
ans.push_back(1);
for (auto iter = result.rbegin(); iter != result.rend(); ++iter) {
ans.push_back(ans.back() + *iter);
}
std::reverse(ans.begin(), ans.end());
std::cout << ans.size() << '\n';
for (auto const &iter: ans) {
std::cout << iter << ' ';
}
std::cout << '\n';
}
std::cout << std::flush;
return 0;
}