【CodeForces】702B - Powers of Two（二分）

110 阅读 0 评论 73 点赞

我是靠谱客的博主无情翅膀，最近开发中收集的这篇文章主要介绍【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).

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.

以后见到这种数据又大又要找有多少对的要想起来二分，2的31次方大概就能包括到两个最大的数之和，所以从第一个数开始，从2的1~31次方依次枚举，二分找有多少满足的就行了，这个找有多少个数用upper_bound - lower_bound就行了。

另外：注意数的精度。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MAX 100000
int main()
{
	int n;
	__int64 num[MAX+11];
	while (~scanf ("%d",&n))
	{
		for (int i = 1 ; i <= n ; i++)
			scanf ("%I64d",&num[i]);
		sort(num+1 , num+1+n);
		__int64 ans = 0;
		for (int i = 1 ; i <= n ; i++)
		{
			for (int j = 1 ; j <= 31 ; j++)
			{
				__int64 t = ((__int64)1<<j) - num[i];
				ans += upper_bound(num+1+i , num+1+n , t) - lower_bound(num+1+i , num+1+n , t);
			}
		}
		printf ("%I64dn",ans);
	}
	return 0;
}