题目链接: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; }
Comments NOTHING