题目描述

作为彩虹岛上最擅长打铁的人，???今天一共打了?块大小为1的铁。为了保存这些铁块，他打算制作若干个箱子。其中，第1个箱子的容量为1(可装1块铁)，之后每个箱子的容量都是它前一个箱子的容量的2倍。

但是他只会打铁，并不擅长制作箱子。制作完成后，他发现第1个箱子的容量是2(而不是1)，之后每个箱子的容量都比它前一个箱子的容量的2倍少1，即第2个箱子的容量是3 = 2 × 2 − 1，第3个箱子的容量是5 = 3 × 2 − 1，第4个箱子的容量是9 = 5 × 2 − 1，依此类推。

作为一个勤俭节约的人，???想知道能否把这?块铁全部放入箱子中并使得所有装有铁块的箱子都装满了且没有空余。

输入描述:

输入第一行为一个整数?(1 ≤ ? ≤ 100)，表示一共有?组数据。 对于每组测试数据： 第一行为一个整数?(1 ≤ ? ≤ 109)，表示???一共打了?块铁。

输出描述:

对于每组测试数据，如果能够按照要求放进箱子里面则输出“YES”，否则输出“NO”。

示例1

输入

218

输出

NOYES

说明

对于第一组样例，无法按照要求放入箱子中。 对于第二组样例，用容量为3和容量为5的箱子恰好能够放下8块铁。

题解

题意：$2^0+1$、$2^1+1$、$2^2+1$.....这些数，能不能凑出$n$，每个数最多用$1$次。

可以枚举用了几个数，假设用了$x$个数字，那么先将$n$减去$x$，然后检查$n-x$的二进制中是否恰好是$x$个$1$即可。

#include 
          
           using namespace std;int T;long long n;long long lowbit(long long x) {  return x & (-x);}int main() {  scanf("%d", &T);  while(T --) {    scanf("%lld", &n);    int flag = 0;    for(int i = 1; i <= 30; i ++) {      long long x = n - i;      int u = 0;      while(x) {        x = x - lowbit(x);        u ++;      }      if(u == i) {        flag = 1;        break;      }    }    if(flag) {      printf("YES\n");    } else {      printf("NO\n");    }  }  return 0;}