51nod 1675.序列变换

果然有时候还是得老老实实地用莫比乌斯反演公式(即函数反演)来做比较好。
f(x)=i=1nj=1n[gcd(i,j)=x][abi=baj],F(x)=i=1nj=1n[xgcd(i,j)][abi=baj]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)=i=1nμ(i)F(i)f(1) = \sum\limits_{i=1}^n \mu(i)F(i)
然后只要求出 FF 即可。

然后就是喜闻乐见的枚举倍数环节,同时开个桶统计一下即可。

代码:

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
#include <cstdio>
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);
}