# B. Pleasant Pairs Codeforces Solution

Page Contents

B. Pleasant Pairs

You are given an array a1,a2,…,ana1,a2,…,an consisting of nn distinct integers. Count the number of pairs of indices (i,j)(i,j) such that i<ji<j and ai⋅aj=i+jai⋅aj=i+j.Input

The first line contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases. Then tt cases follow.

The first line of each test case contains one integer nn (2≤n≤1052≤n≤105) — the length of array aa.

The second line of each test case contains nn space separated integers a1,a2,…,ana1,a2,…,an (1≤ai≤2⋅n1≤ai≤2⋅n) — the array aa. It is guaranteed that all elements are distinct.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.Output

For each test case, output the number of pairs of indices (i,j)(i,j) such that i<ji<j and ai⋅aj=i+jai⋅aj=i+j.

Example

input

```3
2
3 1
3
6 1 5
5
3 1 5 9 2
```

output

```1
1
3
```

Note

For the first test case, the only pair that satisfies the constraints is (1,2)(1,2), as a1⋅a2=1+2=3a1⋅a2=1+2=3

For the second test case, the only pair that satisfies the constraints is (2,3)(2,3).

For the third test case, the pairs that satisfy the constraints are (1,2)(1,2), (1,5)(1,5), and (2,3)(2,3).

Program:

``````#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

#define F first
#define S second
#define inf 1e16

int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll tc; cin >> tc;
const ll N = 200005;
vector<vector<ll>> primes(N + 1);
for(ll i = 1; i <= N; i++){
for(ll j = i; j <= N; j += i){
primes[j].push_back(i);
}
}

while(tc--){
ll n; cin >> n;
vector<ll> v(n);
unordered_map<ll, ll> mp;
for(int i = 0; i < n; i++) cin >> v[i], mp[v[i]] = i + 1;
ll ans = 0;
for(ll i = 2; i <= 2*n - 1; i++){
for(auto &j: primes[i]){
if(j >= (i/j)) break;
auto it1 = mp.find(j), it2 = mp.find(i/j);
if(it1 != mp.end() && it2 != mp.end() && (it1 -> second) + (it2 -> second) == i){
ans++;
}
}
}
cout << ans << '\n';
}
return 0;
}
``````