思路
刚拿到题，想了一些方法但都被推翻了，在这里列举出来，并给出反例：
-
每次减去最小的因数，反例：\(1024\) 等形如 \(a^k\) 的数，每次都会减去 \(a\) 导致 \(a\) 的出现次数超过 \(2\) 次。
-
每次减去大于等于 \(\sqrt x\) 的因子，\(x\) 为目前的数，并特判指数的情况，反例：\(35\) 等由两个质数相乘的数，会减去多次较大的质数，导致出现次数超 \(2\) 次。
-
记忆化搜索，没反例，但是时间复杂度会超。
在经过多次尝试后，我终于想到了一点，如果 \(x\) 是形如 \(2^k\) 的数，可以每次减去 \(\frac x 2\) 直到变为 \(1\)。
那么，我们尝试把给定的数变为 \(2^k\) 的形式。
发现给定的数离 \(2^k\) 的差距就只是二进制下除了最高位的 \(1\)。
所以可以先每次减去 \(\operatorname{lowbit}(x)\)，直到 \(x\) 为 \(2^k\)，然后再每次减去 \(\frac x 2\)。
发现前半部分最多减去了一次 \(2^l\) 其中 \(0\le l <k\)。
然后后半部分会减去 \(2^m\) 其中 \(0\le m <k\) 各一次。
所以不会超过 \(2\) 次的限制。
AC code
#include<bits/stdc++.h>
using namespace std;
inline int lowbit(int x){return x&(-x);}
int T,n,ans[1005],cnt,nn;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n),cnt=0,nn=n;
while(n&(n-1))//判断是否变为2^k
{
ans[++cnt]=lowbit(n),n-=lowbit(n);//记录操作
}
while(n>1) ans[++cnt]=n/2,n/=2;//每次减去n/2
printf("%d\n",cnt+1);//操作cnt次，共cnt+1个数
for(int i=1;i<=cnt;++i)
{
printf("%d ",nn),nn-=ans[i];
}
printf("%d\n",nn);
}
return 0;
}