Problem Link : CodeChef: Practical coding for everyone
We want to find all the pairs in the array such that (a[i]*a[j])%(i*j)==0 .
A simple bruteforce would be 2 loops where we would check whether the above condition holds for the corresponding pair.
Bruteforce approach will give a TLE because of the given constraints. What can we do next?
At first, we eliminate the common factors between a[i] and i by dividing them with their HCF because no matter what pair we select, those factors would always be common and hence we don’t need to consider them for our calculation.
We create a 2-D dp which will store (availableFactors,requiredFactors) for each number.
For each element in the array, we will calculate all its factors by using square root decomposition. Now to calculate the answer, for each factor, we’ll check whether we have encountered an element where it requires a factor of my current element and has the required factors for the current index to make it an interesting pair and add all such occurances to our answer.
Next we’ll store the available and required factors in the DP for proccessing the further elements.
Here is the code , it is mostly self explanatory. Please let me know if you have any doubts, I’ll be happy to help 
#include <bits/stdc++.h>
#define ll long long
const int mod = 1000000007;
const int modx = 998244353;
#define readi(x) scanf("%d", &x)
#define reads(x) scanf("%s", x)
#define readl(x) scanf("%I64d", &x)
#define rep(i, n) for (auto i = 0; i < n; i++)
#define rep1(i, a, b) for (auto i = a; i < b; i++)
#define rep2(i, a, b) for (auto i = b; i >= a; i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define bpc(x) __builtin_popcount(x)
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pdd pair<double, double>
#define pic pair<int, char>
#define ddouble long double
#define PI 3.1415926535
#define endl "\n"
#define vi vector<int>
#define vll vector<long long>
#define vvi vector<vi>
#define vvll vector<vll>
#define all(x) x.begin(), x.end()
#define prod(x, y) ((x % mod) * (y % mod)) % mod
#define add(x, y) ((x % mod) + (y % mod)) % mod
#define ub(a, b) upper_bound(all(a), b)
#define lb(a, b) lower_bound(all(a), b)
#define pqs priority_queue<int, vector<int>, greater<int>>
#define pqb priority_queue<int>
#define mii map<int, int>
#define mll map<ll, ll>
const ll inf = (1e18);
using namespace std;
void inputfromtext()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
#define int long long
unordered_map<int, vector<int>> divisors;
vector<int> getDivisors(int n)
{
if (!divisors[n].empty())
return divisors[n];
for (int i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
divisors[n].pb(i);
if (i * i != n)
divisors[n].pb(n / i);
}
}
return divisors[n];
}
void solve()
{
int n;
cin >> n;
vector<pii> a(n + 1);
rep1(i, 1, n + 1)
{
int inp;
cin >> inp;
int hcf = __gcd(inp, (int)i);
a[i] = {inp / hcf, i / hcf};
}
ll ans = 0;
unordered_map<int, unordered_map<int, int>> dp;
rep1(i, 1, n + 1)
{
auto divs = getDivisors(a[i].ff);
int required = a[i].second;
for (auto available : divs)
{
ans += dp[required][available];
}
for (auto available : divs)
{
dp[available][required]++;
}
}
cout << ans << endl;
return;
}
#undef int
int main()
{
inputfromtext();
ll tt = 1;
cin >> tt;
for (ll testcase = 1; testcase <= tt; testcase++)
{
//cout << "Case #" << testcase << ": ";
solve();
}
return 0;
}