蒟蒻的题目笔记+1

一直在想什么样的数会不满足这样的等差数列和，就是没想到2的次幂（日常看题解豁然开朗 + 锤脑瓜）

所以这道题的关键便是：2的次幂不可以被表示为连续的数字之和

证明：

某个数可以用连续的整数相加表示，意味着该数一定为某个公差为1的自然数的等差数列的和。
众所周知：等差数列的前n项和为 n * a1 + (n * (n - 1)) / 2 * d (这里d为1)
那么假设n * a1 + (n * (n - 1)) / 2 = 2 ^ x;
基于2的次幂的性质（就是偶数啦），2的次幂不可被分解为奇数与偶数的乘积来表示
那证明的时候要凑乘法！
所以可以化为n * (2 * a1 + n - 1) = 2 ^ (n + 1)
由于n - 1与n奇偶性一定不相同，而2a1为偶数，那么左式一定为奇数乘偶数的形式
而右式一定为偶数，无法表示为左式的形式（即便左式为偶数，但一定不为2的次幂的形式）
所以这样的前n项和一定不会是2的次幂的数
而其他数则都有可能（证明略，可以看看大佬题解）

既然是2的次幂，那么又众所周知：2的次幂二进制数1的数量为1

所以用lowbit函数计算每一个数二进制1的个数，二进制数1的个数为1的数的数量就是答案

开long long 啊！！！

#include <iostream> 
using namespace std;
typedef long long LL;
const int N = 2 * 1e5 + 10;
LL a[N];
int n;
int lowbit(LL x){
    int res = 0;
    while(x){
        x -= (-x & x);
        res++;
    }
    return res;
}
int main(){
    cin >> n;
    int res = 0;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++){
        if(lowbit(a[i]) == 1){
            res++;
        }
    }
    cout << res;
    return 0;
}