Educational Codeforces Round 15

Educational Codeforces Round 15_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 x exists 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

input

3
1 1 1

output

Note

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.

题意：

给你n个数，问你有多少对满足a[i]+a[j]为2的次方.

题解：

首先，我们考虑他们能加起来的sum最多也就32个，0~2^31，所以我们对每一个a[i]都枚举sum-a[i],然后二分找这个数集里面有多少个满足条件，这里要考虑特殊的情况，如果sum-a[i]=a[i],那么你找到满足条件的个数要减1，然后最后ans要除2，因为sum-a[i]=a[j],sum-a[j]=a[i]，算了2次

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 const int N=1e5+7;
 7 int a[N];
 8 int main(){
 9     int n;
10     ll ans=0;
11     scanf("%d",&n);
12     F(i,1,n)scanf("%d",a+i);
13     sort(a+1,a+1+n);
14     F(i,1,n)
15     {
16         for(int j=30;j>=0;j--){
17             int now=1<<j;
18             if(now<a[i])break;
19             int tmp=now-a[i];
20             int pos1=lower_bound(a+1,a+1+n,tmp)-a;
21             int pos2=upper_bound(a+1,a+1+n,tmp)-a;
22             if(a[pos1]==tmp){
23                 ans+=pos2-pos1;
24                 if(tmp==a[i])ans--;
25             }
26         }
27     }
28     ans/=2;
29     printf("%I64d
",ans);
30     return 0;
31 }

View Code