702B.md (1073B)
1 Source: https://codeforces.com/problemset/problem/702/B 2 3 B. Powers of Two 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given *n* integers *a*1, *a*2, ..., *a**n*. Find the number of pairs of indexes *i*, *j* (*i* < *j*) that *a**i* + *a**j* is a power of 2 (i. e. some integer *x* exists so that *a**i* + *a**j* = 2*x*). 22 23 Input 24 25 The first line contains the single positive integer *n* (1 ≤ *n* ≤ 105) — the number of integers. 26 27 The second line contains *n* positive integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 109). 28 29 Output 30 31 Print the number of pairs of indexes *i*, *j* (*i* < *j*) that *a**i* + *a**j* is a power of 2. 32 33 Examples 34 35 Input 36 37 ``` 38 4 39 7 3 2 1 40 ``` 41 42 Output 43 44 ``` 45 2 46 ``` 47 48 Input 49 50 ``` 51 3 52 1 1 1 53 ``` 54 55 Output 56 57 ``` 58 3 59 ``` 60 61 Note 62 63 In the first example the following pairs of indexes include in answer: (1, 4) and (2, 4). 64 65 In the second example all pairs of indexes (*i*, *j*) (where *i* < *j*) include in answer.