51nod 1675 序列变换

果然有时候还是得老老实实地用莫比乌斯反演公式（即函数反演）来做比较好。
设 f(x)=n∑i=1n∑j=1[gcd(i,j)=x][abi=baj],F(x)=n∑i=1n∑j=1[x|gcd(i,j)][abi=baj]。

显然所求即 f(1)=n∑i=1μ(i)F(i)。
然后只要求出 F 即可。
有 F(x)=n∑i=1n∑j=1[x|gcd(i,j)][abi=baj]=∑x|i∑x|j[abi=baj]

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

代码：

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