[牛客竞赛数学专题班积性函数]C.序列（莫比乌斯反演 + 线性筛）

题目链接：C-序列_牛客竞赛数学专题班积性函数（积性函数概念、欧拉筛求积性函数、莫比乌斯反演） (nowcoder.com)

Pre-Knowledge

前置知识：《莫比乌斯反演入门以及简单例题讲解》

Problem

给定两个长度为\(n\)的数组\(a\)和\(b\)，求下面这个和式的值：

$$\sum\limits_{x=1}^n\sum\limits_{y=1}^n[gcd(x,y)=1][a_{b_x} = b_{a_y}]$$

根据莫反套路，设两个函数：

$$F(n)：当gcd(x, y)为n的倍数时[a_{b_x} = b_{a_y}]的对数$$

$$f(n)：当gcd(x,y)=n时[a_{b_x} = b_{a_y}]的对数$$

定义完之后就可以得到两个函数的关系了：

$$F(n) = \sum\limits_{n|d}f(d)$$

开始莫反！

$$f(n) = \sum\limits_{n|d}\mu( \frac{d}{n})F(d)$$

我们要求的\(ans = f(1)\)，所以：

$$ans = f(1) = \sum\limits_{d=1}^n \mu(d) F(d)$$

将\(d\)用\(i\)换掉：

$$ans = \sum\limits_{i=1}^n \mu(i) F(i)$$

现在只需要处理出\(\mu\)和\(F\)两个函数即可。

\(\mu\)可以通过线性筛直接筛出来，\(F\)函数可以通过一个\(O(nlogn)\)的算法算出来。

枚举\(i\)和\(i的倍数j\)，此时一定满足条件\(gcd(i, j) = k * i\)，接下来记录\(a_{b_j}\)的出现次数，再将\(b_{a_j}\)出现的次数加入到\(F(i)\)中。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;
//杜教筛+线性筛优化，复杂度O(N^(2/3))
int mu[maxn], a[maxn], b[maxn], F[maxn], cnt[maxn];

void init(int N = maxn - 1)//N = maxn - 1
{
    bitset<maxn> vis;
    vector<int> prim;
    vis[0] = vis[1] = true;
    mu[1] = 1;
    for(int i = 2;i <= N; ++ i)
    {
        if(!vis[i])prim.push_back(i), mu[i] = -1;
        
        for(auto &j : prim)
        {
            if(i * j > N)break;
            vis[i * j] = true;
            if(i % j == 0)break;
            mu[i * j] = mu[i] * mu[j];
        }
    }
}

signed main()
{
	int n;scanf("%lld", &n);
	init(n);
	for(int i = 1;i <= n; ++ i)scanf("%lld", a + i);
	for(int i = 1;i <= n; ++ i)scanf("%lld", b + i);
	
    for(int i = 1;i <= n; ++ i)
    {
        for(int j = i;j <= n;j += i)cnt[a[b[j]]] ++;
        for(int j = i;j <= n;j += i)F[i] += cnt[b[a[j]]];
        for(int j = i;j <= n;j += i)cnt[a[b[j]]] = 0;
    }
    
	int ans = 0;
	for(int i = 1;i <= n; ++ i)ans += mu[i] * F[i];
	printf("%lld\n", ans);
	return 0;
}