Educational Codeforces Round 15 B. Powers of Two （数学）

101 阅读 0 评论 67 点赞

我是靠谱客的博主美满心情，这篇文章主要介绍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 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

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.

题解：感觉没什么好说的。。。

AC代码：

#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MP(x,y) make_pair(x,y)  
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }  
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
int read()
{
	int v = 0, f = 1;
	char c =getchar();
	while( c < 48 || 57 < c ){
		if(c=='-') f = -1;
		c = getchar();
	}
	while(48 <= c && c <= 57) 
		v = v*10+c-48, c = getchar();
	return v*f;
}
map<int,int>m;
int n,a;
ll ans;
int main()
{	
	cin>>n;
	for(int i =0; i<n; i++)
	{
		cin>>a;
		for(int j=1; j<=31; j++)
		{
			ans+=m[(1LL<<j)-a];					
		}		
		m[a]++;
	}
	printf("%I64dn",ans);
	return 0;
}