# PBinfo #2239 – pow2 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Se consideră un șir a[1], a[2],…, a[n] de numere naturale nenule. 

Cerința
Să se determine câte perechi de indici (i, j), 1 ≤ i < j ≤ n, există cu proprietatea că suma a[i] + a[j] este egală cu o putere a lui 2.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi cele n numere naturale nenule, separate prin spații.

Date de ieșire
Programul va afișa pe ecran un singur număr natural reprezentând numărul de perechi de indici distincți (i, j) cu proprietatea că suma a[i] + a[j] este egală cu o putere a lui 2.

Restricții și precizări

2 ≤ n ≤ 100.000
1 ≤ a[i] ≤ 1.000.000.000, pentru orice i = 1..n
Numerele care sunt puteri ale lui 2 sunt 1, 2, 4, 8, 16, 32, …

Exemplu:
Intrare

4
3 5 3 13
Ieșire

4
Explicație
Cele patru perechi de indici sunt: (1,2), (1,4), (2,3), (3,4).

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define H 100003
using namespace std;
vector<pair<int,int>> T[H];
int n,i,x[H],p[32],c,v,w,j,h,C;
long long sol;
int main()
{
    cin >> n;
    for(i=1;i<=n;i++)
        cin >> x[i];
    sort(x+1,x+n+1);
    p[0]=1;
    for(i=1;i<=31;i++)
        p[i]=2*p[i-1];
    for(i=n;i;)
    {
        v=x[i];c=0;
        while(x[i]==v)
        {
            i--;c++;
        }
        if(v==(v&(-v)))
            sol+=1LL*c*(c-1)/2;
        for(j=31;;j--)
        {
            w=p[j]-v;
            if(w<=v)
                break;
            h=w%H;
            C=0;
            vector<pair<int,int>>::iterator it;
            for(it=T[h].begin();it!=T[h].end();it++)
                if(it->first==w)
                {
                    C=it->second;
                    break;
                }
            sol+=1LL*c*C;
        }
        h=v%H;
        T[h].push_back(make_pair(v,c));
    }
    cout << sol;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2239)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2239/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2239/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)