cf702B Powers of Two

83 阅读 0 评论 55 点赞

我是靠谱客的博主土豪盼望，最近开发中收集的这篇文章主要介绍cf702B 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

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个数字，问有多少对数字加起来刚好是2的k次方。

这还用说？枚举个k再枚举个a[i]然后看看有没有2^k-a[i]这个数就好了

这里我为了防被x没用hash用了二分

不过要考虑一个数字出现很多次的情况，或者你要找的刚好就是这个数的情况

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<set>
 8 #include<map>
 9 #include<ctime>
10 #define LL long long
11 #define inf 0x7ffffff
12 #define pa pair<int,int>
13 #define pi 3.1415926535897932384626433832795028841971
14 using namespace std;
15 inline LL read()
16 {
17     LL x=0,f=1;char ch=getchar();
18     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
19     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
20     return x*f;
21 }
22 inline void write(LL a)
23 {
24     if (a<0){printf("-");a=-a;}
25     if (a>=10)write(a/10);
26     putchar(a%10+'0');
27 }
28 inline void writeln(LL a){write(a);printf("n");}
29 int n,sav;
30 LL ans;
31 int a[100010];
32 int rep[100010];
33 int bin[110];
34 inline bool bsearch(int l,int r,int x,int dat)
35 {
36     if (dat<=0)return 0;
37     if (l>r)return 0;
38     int ans=-1;
39     while (l<=r)
40     {
41         int mid=(l+r)>>1;
42         if (a[mid]==dat){ans=mid;break;}
43         if (a[mid]>dat)r=mid-1;
44         if (a[mid]<dat)l=mid+1;
45     }
46     sav=ans;
47     return (ans!=x||ans==x&&rep[x]>1)&&a[ans]==dat;
48 }
49 int main()
50 {
51     n=read();
52     bin[0]=1;
53     for (int i=1;i<31;i++)bin[i]=bin[i-1]*2;
54     for(int i=1;i<=n;i++)a[i]=read();
55     sort(a+1,a+n+1);
56     int cur=0;
57     for(int i=1;i<=n;i++)
58     {
59         if (a[i]!=a[i-1])a[++cur]=a[i],rep[cur]=1;
60         else rep[cur]++;
61     }
62     n=cur;
63     for(int i=1;i<=n;i++)
64     {
65         for (int j=0;j<31;j++)
66             if (bsearch(i,n,i,bin[j]-a[i]))
67             {
68                 if (sav==i)ans+=(LL)rep[i]*(rep[i]-1)/2;
69                 else ans+=(LL)rep[i]*rep[sav];
70             }
71     }
72     printf("%lldn",ans);
73 }