Möhtəşəm Cütlüklər#12265

Möhtəşəm Cütlüklər (Həll təhlili)

Problem Müəllifi:	De3b0o
Hazırlayan:	De3b0o
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Bir cüt ( $i, j$ ) möhtəşəm olması üçün aşağıdakı şərti ödəməlidir:

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

Bir cüt ( $i, j$ ) ( $i, j \geq 1000$ i,j \ge 1000) möhtəşəm ola bilməz, çünki bu halda $i \cdot j \geq 1 0^{6} \geq a_{i} + a_{j}$ i \cdot j \ge 10^6 \ge a_i + a_j.

Beləliklə, hər $j$ üçün, cütlərin ( $i, j$ ) ( $1 \leq i \leq min (j, 1000)$ 1 \le i \le \min(j,1000)) möhtəşəm olub olmadığını yoxlaya bilərik.

Komplekslik $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";
    }
}