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;
}