You are given an array a1,a2,…,an consisting of n distinct integers. Count the number of pairs of indices (i,j) such that i<j and ai?aj=i+j.
Input
The first line contains one integer t (1≤t≤10^4) — the number of test cases. Then t cases follow.
The first line of each test case contains one integer n (2≤n≤10^5) — the length of array a.
The second line of each test case contains n space separated integers a1,a2,…,an (1≤ai≤2?n) — the array a. It is guaranteed that all elements are distinct.
It is guaranteed that the sum of n over all test cases does not exceed 2?10^5.
Output
For each test case, output the number of pairs of indices (i,j) such that i<j and ai?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), as a1?a2=1+2=3
For the second test case, the only pair that satisfies the constraints is (2,3).
For the third test case, the pairs that satisfy the constraints are (1,2), (1,5), and (2,3).
题意：
找出一个数组a[n]中有几对（a[i]，a[j]）满足 a[i] * a[j] = i + j (i < j)，其中数组a[n]中的元素不重复。
思路：
暴力 + 剪枝
具体的剪枝思路：
因为是 a[i] * a[j] ，然后这里是根据 a[i] 来找 a[j] ，可以知道 i + j 一定是 a[i] 的倍数，i 是不变的，所以 j 的增加量一定是a[i] 的倍数。
ps：我一开始不知道咋剪枝，只剪了一点点还是TLM ……orz……然后后面还是一直wa，是因为数组没开long long ，（因为运算的数据会超过int的范围QAQ）
#include<iostream>
#include<cmath>
#include<algorithm>
#define bug(a) cout << a << "*" << endl;
using namespace std;typedef long long ll;
const int N = 2e5 + 5;
ll a[N];int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while(T--){
int n;cin >> n;ll ans = 0;for(int i = 1; i <= n; ++i)cin >> a[i];for(int i = 1; i <= n; ++i){
for(int j = a[i] - i; j <= n; j += a[i]){
if(j <= i)continue;if(a[i] * a[j] == i + j)ans++;}}cout << ans << endl;}return 0;}