codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1541B.md (1406B)


      1 Source: https://codeforces.com/problemset/problem/1541/B
      2 
      3 B. Pleasant Pairs
      4 
      5 time limit per test
      6 
      7 2 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 an array $a_1, a_2, \dots, a_n$ consisting of $n$ distinct integers. Count the number of pairs of indices $(i, j)$ such that $i \lt j$ and $a_i \cdot a_j = i + j$.
     22 
     23 Input
     24 
     25 The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then $t$ cases follow.
     26 
     27 The first line of each test case contains one integer $n$ ($2 \leq n \leq 10^5$) — the length of array $a$.
     28 
     29 The second line of each test case contains $n$ space separated integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 2 \cdot n$) — the array $a$. It is guaranteed that all elements are distinct.
     30 
     31 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     32 
     33 Output
     34 
     35 For each test case, output the number of pairs of indices $(i, j)$ such that $i \lt j$ and $a_i \cdot a_j = i + j$.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 3
     43 2
     44 3 1
     45 3
     46 6 1 5
     47 5
     48 3 1 5 9 2
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 1
     55 1
     56 3
     57 ```
     58 
     59 Note
     60 
     61 For the first test case, the only pair that satisfies the constraints is $(1, 2)$, as $a_1 \cdot a_2 = 1 + 2 = 3$
     62 
     63 For the second test case, the only pair that satisfies the constraints is $(2, 3)$.
     64 
     65 For the third test case, the pairs that satisfy the constraints are $(1, 2)$, $(1, 5)$, and $(2, 3)$.