codeforces 702B - 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).

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).

Print the number of pairs of indexes i, j (i < j) that ai + aj is a power of 2.

In the first example the following pairs of indexes include in answer: (1, 4) and (2, 4).

In the second example all pairs of indexes (i, j) (where i < j) include in answer.

a[i]+a[j]==2^x, 反过来就是2^x-a[i]要在输入的范围之内，x的范围从1到30，总的时间复杂度降为O(n)*30, map<a, b>表示a出现了b次；

AC代码：

# include <iostream>
# include <map>
using namespace std;
map<int, int > m;
int c[100010], a[100010];
int main(){int n, i, j, k;cin>>n;for(i=1; i<=n; i++){cin>>a[i];m[a[i]]++;}long long int cnt=0;for(i=1; i<=n; i++){for(j=1; j<=30; j++){int num=(1<<j)-a[i];if(m[num]){if(num==a[i]){cnt=cnt+m[num]-1;}else{cnt=cnt+m[num];}}}}cout<<cnt/2;return 0;
}