Величні пари#12265

Величні пари (Розбір)

Автор проблеми:	De3b0o
Підготовлено:	De3b0o
Редагував:	Hasan Saleh (MathModel)

Рішення

Щоб пара ( $i, j$ ) була величною, вона повинна задовольняти наступну умову:

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

Пара ( $i, j$ ), де ( $i, j \geq 1000$ i,j \ge 1000) не може бути величною, оскільки тоді $i \cdot j \geq 1 0^{6} \geq a_{i} + a_{j}$ i \cdot j \ge 10^6 \ge a_i + a_j.

Отже, ми можемо для кожного $j$ перевірити, чи є пари ( $i, j$ ) ( $1 \leq i \leq min (j, 1000)$ 1 \le i \le \min(j,1000)) величними.

Складність $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";
    }
}