B. Pleasant Pairs Codeforces Solution

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;
}

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment