cf1864C. Divisor Chain

发布时间 2023-11-17 23:25:36作者: gan_coder

https://codeforces.com/contest/1864/problem/C

思维越来越僵化了
假如\(n=2^k\),直接每次/2就行。
否则,我们可以考虑如何转化成上面的情况
\(n=2^k x\),那么我们显然可以转移到\(n=2^k (x-1)\),因为x是奇数,所以2的次幂会加一,最后变成\(2^k\)次方的时候,每个数最多出现两次,正好符合题意。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<ctime>
#define A puts("YES")
#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll mo=998244353;
const ll inf=1ll<<60;
const int N=1e5+5;
int p[N],tot,ans,b[N],now;
bool vis[N];
int n;
void work(int n){
	int cnt=0;
	int m=n;
	while (n%2==0) {
		n/=2;
		cnt++;
	}
	
	if (n==1) {
		fd(i,cnt,0) b[++ans]=1<<i;
		return; 
	}
	
	b[++ans]=m;
	work((m/(1<<cnt)-1) *(1<<cnt));
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
		
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d",&n);
		ans=0;
		work(n);
		
		printf("%d\n",ans);
		fo(i,1,ans) printf("%d ",b[i]);
		printf("\n");
	}

	return 0;
}