Majestic Pairs#12265

Majestic Pairs (Editorial)

Problem Author:	De3b0o
Prepared by:	De3b0o
Edited by:	Hasan Saleh (MathModel)

Solution

For a pair ( $i, j$ ) to be majestic, it must satisfy the following condition:

$a_{i}$ a_i $+$ $a_{j}$ a_j $=$ $i$ $\cdot$ $j$

A pair ( $i, j$ ) where ( $i, j \geq 1000$ i,j \ge 1000) can't be majestic because then $i \cdot j \geq 1 0^{6} \geq a_{i} + a_{j}$ i \cdot j \ge 10^6 \ge a_i + a_j.

So we can for each $j$ , check if the pairs ( $i, j$ ) ( $1 \leq i \leq min (j, 1000)$ 1 \le i \le \min(j,1000)) are majestic.

Complexity $O (1000 \cdot \sum (n))$ \mathcal{O}(1000 \cdot \sum(n)).


#include<bits/stdc++.h>
#define ll long long
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
using namespace std;

const ll N = 1e5+9;

ll n,ans;
ll a[N];

int main()
{
    d3
    ll T;
    cin >> T;
    while(T--)
    {
        cin >> n;
        for(int i = 1 ; n>=i ; i++)
            cin >> a[i];
        ans=0;
        for(int i = 1 ; n>=i ; i++)
        {
            for(int j = 1 ; min(i,1000)>=j ; j++)
            {
                if(a[i]+a[j]==i*j)
                    ans++;
            }
        }
        cout << ans << "\n";
    }
}