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).
OutputPrint 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
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.
题意找数组中有多少对数加起来是2的x次方思路 给的数大小是1e9，和在2的30次方之内，二分法#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x[35],a[101000];
int main()
{for(int i=1;i<=30;i++){x[i] = pow(2,i);//cout<<x[i]<<endl;}ll n,ans,num;cin>>n;ans = 0;for(int i=0;i<n;i++){scanf("%lld",&a[i]);}sort(a,a+n);for(int i=0;i<n;i++){for(int j=1;j<=30;j++){num = x[j] - a[i]; //二分法找符合的个数if(num<1||num>1e9)continue;int s = lower_bound(a+i+1,a+n,num)-a;//第一个等于num的位置int e = upper_bound(a+i+1,a+n,num)-a;//第一个大于num的位置ans += e-s;}}printf("%lld\n",ans);return 0;
}