题解 【CF1005C Summarize to the Power of Two】

Solution

题目就是这个意思：
给定一个数列 $a$，求满足 $2^q=a_i+a_j$ ($1\le i,j\le n,q\in Z$) 不成立的数据组数。
十分简单，首先我们考虑这个等式，它可以换成 $a_j = 2^q-a_i$，其中我们暴力枚举 $a_i$，然后再暴力计算出第一个 $q$，往后到数据极限，如果其中有一组数据满足等式，那么这一个 $a_i$ 一定不能记录进我们的答案，否则就可以，那么怎么判断满足等式呢？显然，我们考虑桶，用 map 或者 hash 都可以满足要求。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1.2e5 + 9;

typedef long long ll;
#define gc getchar
inline ll read() {
    ll c = gc(), t = 1, n = 0;
    while(isspace(c)) { c = gc(); }
    if(c == '-') { t = -1, c = gc(); }
    while(isdigit(c)) { n = n * 10 + c - '0', c = gc(); }
    return n * t;
}
#undef gc

map <int,int> mp;
int a[N],n,q,flag,ans = 0;

int main() {
    n = read();
    for(int i = 1;i <= n;i++) {
        a[i] = read(); mp[a[i]]++;
    }
    for(int i = 1;i <= n;i++) {
        mp[a[i]]--;
        q = 0; flag = 0;
        while((1 << q) <= a[i]) q++;
        for(; q <= 31; q++) {
            if(mp[(1 << q) - a[i]]) { flag = 1; break; }
        }
        if(!flag) ++ans;
        ++mp[a[i]];
    }
    printf("%d\n",ans);
    return 0;
}