P7071 [CSP-J2020] 优秀的拆分 题解

二进制

"优秀的拆分"如果存在，则代表 $n$ 的二进制最低位不是 $1$.

$\because 2^0 = 1$

$\therefore$ 当 $n$ 的二进制最低位为 $1$ 时，不存在优秀的拆分.

即 $n$ 不是奇数.

上述条件判断完后，就可以从 $2$ 的 $30$ 次方开始模拟( int 的上限是 $2^{31}-1$).

代码

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

int n;

int main() {
	scanf("%d", &n);
	if (n % 2 == 1) printf("-1"); // n 为奇数不存在优秀的拆分
	else {
		int p = 30;
		while (n) { // 从 2^30 开始枚举
			int power = pow(2, p);
			if (power <= n) { // n 能够减去 power
				printf("%d ",power);
				n -= power;
			}
			p--; // 次数降低
		}
	}
	return 0;
}