CodeForces - 702B Powers of Two

74 阅读 0 评论 49 点赞

我是靠谱客的博主认真机器猫，最近开发中收集的这篇文章主要介绍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 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.

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.

二分模拟

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
long long a[100050];
long long d[32];
int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	int ans=1;
	for(int i=0;i<31;i++) {
		d[i]=ans;
		ans*=2;
	}
	long long maxn=0;
	for(int i=0;i<n;i++) {cin>>a[i];
	maxn=max(maxn,a[i]);
	}
	sort(a,a+n);
	long long ssd=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<31;j++)
		{
			int p=d[j]-a[i];
			if(p>maxn) break;
			if(p<0) continue;
			long long l=i+1,r=n-1;
			long long id=-1;
		    int tp1 = lower_bound(a+i+1, a+n, p)-a;
            int tp2 = upper_bound(a+i+1, a+n, p)-a;
             if(tp1 == n)
              continue;
            int tmp = tp2 - tp1;
              ssd += tmp;
		}
	}
	cout<<ssd<<endl;
	return 0;
}