果然有时候还是得老老实实地用莫比乌斯反演公式（即函数反演）来做比较好。
设 \(f(x) = \sum\limits_{i=1}^n \sum\limits_{j=1}^n [\gcd(i,j) = x][a_{b_i} = b_{a_j}],F(x) = \sum\limits_{i=1}^n \sum\limits_{j=1}^n [x|\gcd(i,j)][a_{b_i} = b_{a_j}]\)。
显然所求即 \(f(1) = \sum\limits_{i=1}^n \mu(i)F(i)\)。
然后只要求出 \(F\) 即可。
有 \[\begin{align*}
F(x) & = \sum\limits_{i=1}^n \sum\limits_{j=1}^n [x|\gcd(i,j)][a_{b_i} = b_{a_j}] \\
& = \sum\limits_{x|i}\sum\limits_{x|j} [a_{b_i} = b_{a_j}]
\end{align*}\]
然后就是喜闻乐见的枚举倍数环节，同时开个桶统计一下即可。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using namespace std;
const int N = 1e5;
int n,a[N + 5],b[N + 5],tot[N + 5];
int vis[N + 5],cnt,prime[N + 5],mu[N + 5];
long long f[N + 5],ans;
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
for(register int i = 1;i <= n;++i)
scanf("%d",b + i);
mu[1] = 1;
for(register int i = 2;i <= n;++i)
{
if(!vis[i])
mu[prime[++cnt] = i] = -1;
for(register int j = 1;j <= cnt && i * prime[j] <= n;++j)
{
vis[i * prime[j]] = -1;
if(!(i % prime[j]))
break;
else
mu[i * prime[j]] = -mu[i];
}
}
for(register int i = 1;i <= n;++i)
{
for(register int j = i;j <= n;j += i)
++tot[a[b[j]]];
for(register int j = i;j <= n;j += i)
f[i] += tot[b[a[j]]];
for(register int j = i;j <= n;j += i)
--tot[a[b[j]]];
}
for(register int i = 1;i <= n;++i)
ans += mu[i] * f[i];
printf("%lld\n",ans);
}