本文主要是介绍Powers of Two CodeForces - 702B，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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.
Examples4 7 3 2 1
2
3 1 1 1
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;
}
这篇关于Powers of Two CodeForces - 702B的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
