结论:只要不是2的幂次,就可以成立
证明:写成二进制,不难发现仅有一位为1是永远不能成立的,但凡有两个一,那说明,将这个数除以二总会得到一个奇数,奇数是可以被除二的两个连续的数所表示的。
比如:10 除以二是 5,5是可以由2,3表示的,那么两个5,无非就是在连续的2,3上,再加上前一个数和后一个数,因为2,3的中点是2.5,由于函数的对称性,只要保证均值不变,那么对于两个连续的数来说,前后多一个数,仅仅是扩大了两倍。
对于20来说,除以2就是得到了 10=1,2,3,4 即再扩一下,就变成了 -1,0,1,2,3,4,5,6 和即为20,那么负数怎么处理呢?向右平移两个单位就好了,其它数以此类推
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000010
// 就是一个数一直除二可不可以达到奇数
// 或者说分解质因数中存不存在奇数。。。没必要
int n;
ll a[N];
bool check(ll u){
while(u){
if(u%2){
if(u!=1)return true;
return false;
}
u/=2;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int cnt=0;
for(int i=1;i<=n;i++)if(!check(a[i]))cnt++;
cout<<cnt<<endl;
return 0;
}