Sample Input
6
1 6 2 5 3 4
Sample Output
10
You are given a {1, 2, ..., n}-permutation a[1], a[2], ..., a[n]. How many pairs of integers (i, j) satisfy 1 ≤ i ≤ j ≤ n and gcd(i, j) = gcd(a[i], a[j]) = 1? Here gcd means greatest common divisor.
Input
First line contains an integer n. (1 ≤ n ≤ 200000)
Second line contains n space-separated integers a[1], a[2], ..., a[n] which form a permutation.
Output
One line contains the answer.
题意：给定N的排列a[]，问有多少对(i,j)，满足gdc(i,j)=gcd(a[i],a[j])=1;
思路：我们知道区间互质对统计可以用莫比乌斯来容斥，对于每个数d，其贡献=mu[d]*C(含d的个数,2)；
但是这里有两个条件，可以说是个二维的。 那么，我们枚举第一位的d，然后在第二维里正常的操作。
复杂度：因为每个数在第一维最多被使用log次，第二维也是，所以复杂度不大于N*logN*logN。加上我们有一些减枝，比如mu[i]=0时不操作。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int a[maxn],mu[maxn],pos[maxn],num[maxn],N; vector<int>G[maxn]; ll ans;
void init()
{ rep(i,,N) {
if(i==) mu[]=; G[i].push_back(i);
for(int j=i+i;j<=N;j+=i) mu[j]-=mu[i],G[j].push_back(i);
}
}
ll get(int x)
{
ll res=;
for(int i=x;i<=N;i+=x)
rep(j,,G[a[i]].size()-) num[G[a[i]][j]]++;
for(int i=x;i<=N;i+=x)
rep(j,,G[a[i]].size()-) res+=1LL*(num[G[a[i]][j]]-)*mu[G[a[i]][j]];
for(int i=x;i<=N;i+=x)
rep(j,,G[a[i]].size()-) num[G[a[i]][j]]=;
return res/;
}
int main()
{
scanf("%d",&N); init();
rep(i,,N) scanf("%d",&a[i]),pos[a[i]]=i;
rep(i,,N)
if(mu[i]) ans+=1LL*mu[i]*get(i);
printf("%lld\n",ans+(a[]==));
return ;
}