思维+暴力
思路
1.i+j<=2*n
2.由于a[i] * a[j]=i+j 所以a[i] * a[j]<=2*n
3.由于第二点可以计算出这样的(i,j)对数最多有nlogn对,计算方法便是假设a[i]=1,2,3…n然后计算a[j]的个数,详情可见:
https://codeforces.com/blog/entry/92199
代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5+10;
int t, n;
PII a[N];
int main()
{
cin >> t;
while (t--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a[i]={x,i};
}
sort(a+1,a+n+1);
int res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i].first*a[j].first>2*n)
break;
else if(a[i].second<a[j].second&&a[i].first*a[j].first==a[i].second+a[j].second)
res++;
cout<<res<<endl;
}
return 0;
}