2239 - Pow2

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

Cerință

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

Rezolvare

<syntaxhighlight lang="python" line="1" start="1">

def numar_perechi(n, a):

   # Generăm toate puterile lui 2 până la 2^30
   puteri_de_doi = [2**i for i in range(31)]

   # Inițializăm un contor pentru fiecare număr posibil din șir
   contor = [0]*2000001

   # Inițializăm numărul de perechi cu 0
   numar_perechi = 0

   # Parcurgem fiecare element din lista a
   for i in range(n):
       # Pentru fiecare element, parcurgem lista de puteri ale lui 2
       for putere in puteri_de_doi:
           # Dacă puterea lui 2 este mai mică decât numărul curent, trecem la următoarea putere
           if putere < a[i]:
               continue

           # Calculăm numărul pe care îl căutăm în contor
           numar_cautat = putere - a[i]

           # Dacă numărul căutat este în intervalul contorului
           if numar_cautat <= 2000000:
               # Adăugăm la numărul de perechi numărul de apariții al numărului căutat
               numar_perechi += contor[numar_cautat]

       # Dacă numărul curent este în intervalul contorului
       if a[i] <= 2000000:
           # Incrementăm contorul pentru numărul curent
           contor[a[i]] += 1

   return numar_perechi

1. Citim datele de intrare

n = int(input()) a = list(map(int, input().split()))

1. Apelăm funcția și afișăm rezultatul

print(numar_perechi(n, a))

</syntaxhighlight>

Explicatii

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