题解 【CF1005C Summarize to the Power of Two】
TRZ_2007
2021-04-01 16:32:39
**[题解 【CF1005C Summarize to the Power of Two】](https://www.luogu.com.cn/problem/CF1005C)**
# 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
```cpp
#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;
}
```