B. Powers of Two
You are given n integers a1, a2, ..., an. Find the number of pairs of indexes i, j (i < j) that ai + aj is a power of 2 (i. e. some integer xexists so that ai + aj = 2x).
Input
The first line contains the single positive integer n (1 ≤ n ≤ 105) — the number of integers.
The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ 109).
Output
Print the number of pairs of indexes i, j (i < j) that ai + aj is a power of 2.
Examples
input
4
7 3 2 1
output
2
input
3
1 1 1
output
3
【分析】：仔细读题后发现，ai不会超过10 ^ 9，约等于2 ^ 30，所以我们可以先打出一张2 ^ k的表，然后对于ai，用2 ^ k减去ai，利用二分搜索得到aj的数量，累加即得结果。时间复杂度为O(N)。
【代码】：
#include<bits/stdc++.h> using namespace std;
#define ll long long
#define maxn 100010
ll a[maxn];
int n;
/*
给出一个数组,求出ai + aj等于2的幂的数对个数
*/
int main()
{ while(cin >> n){
ll ans = ;
for(int i=; i<n; i++)
cin >> a[i];
sort(a,a+n);
for(ll i=; i<n; i++){
for(ll j=; j<; j++){
ll t = (<<j) - a[i];
ans += upper_bound(a+i+,a+n,t)-lower_bound(a+i+,a+n,t);
}
}
cout << ans << endl;
}
return ;
}
二分