题目链接：C-序列_牛客竞赛数学专题班积性函数（积性函数概念、欧拉筛求积性函数、莫比乌斯反演） (nowcoder.com) Pre-Knowledge 前置知识：《莫比乌斯反演入门以及简单例题讲解》 Problem 给定两个长度为\(n\)的数组\(a\)和\(b\)，求下面这个和式的值： $$\sum\limits_{x=1}^n\sum\limits_{y=1}^n[gcd(x,y)=1][ […]

在学习莫比乌斯反演之前，需要了解一些前置知识： 整除分块，狄利克雷卷积。 莫比乌斯函数 记作\(\mu(n)\)，定义如下： 其实这个不用太深入理解，莫比乌斯反演的重点其实在于和式的推导和函数的变换，只需要知道这个\(\mu\)函数是可以用杜教筛\(O(n^{\frac{2}{3}})\)预处理出来的就行了，当数据较小的时候可以线性筛。 很多关于gcd的和式都可以转换成含\(\mu\)的简单形式。 […]