EDU15 B. Powers of Two

B. Powers of Two

题意:问,有多少对i,j(i<j). 使得a[i]+a[j]是2的幂次数

思路: 枚举即可 nlognlogn .. 记住开LL吧.

#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
#define debug puts
#define setp cout << fixed << setprecision(3)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int MOD=1e9+7;
const ll INF=1e18+8;
map<ll,ll> mp,c;
ll a[N];
int main(void){
    FAST_IO;
    int n;
    cin >> n;
    for(int i=1;i<=n;i++)   cin >> a[i],c[a[i]]++;
    for(ll i=2;i<=1e12;i=i*2)    mp[i]=1;
    sort(a+1,a+1+n);
    ll cnt=0;
    for(int i=1;i<=n;i++){
        for(auto t:mp){
            if(t.F-a[i]<0)  continue;
            ll pos1=upper_bound(a+i+1,a+1+n,t.F-a[i])-a;
            ll pos2=lower_bound(a+i+1,a+1+n,t.F-a[i])-a;
            cnt+=pos1-pos2;
        }
    }
    cout << cnt << endl;
    return 0;
}

最后

以上就是动人故事为你收集整理的EDU15 B. Powers of Two的全部内容，希望文章能够帮你解决EDU15 B. Powers of Two所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。