莫比乌斯反演
警告，本文含有大量数学公式
莫比乌斯函数
对于正整数\(N\)，我们都可以将它进行唯一分解\(P_1^{c_1}P_2^{c_2}...P_k^{c_k}\)
我们就用\(\mu\)
注：\(\exists\)表示存在
\[\mu(N)= \begin{cases} 0, \exists i \in [1,k], c_i>1\\ 1, \forall i \in [1,k], c_i=1,(k为偶数)\\ -1, \forall i \in [1,k], c_i=1,(k为奇数) \end{cases} \]用代码求
#include
using namespace std;
void mobius(int n) {
for (int i = 1; i <= n; i++) {
miu[i] = 1;
vis[i]= false;
}
for (int i = 2; i <= n; i++) {
if(vis[i] == true)
continue;
miu[i] = -1;
//质数自己 ,-1
for (int j = 2*i; j <= n; j+=i) {
vis[j] = true;
if(j % (i*i) == 0)
miu[j] = 0; else
miu[j] *= -1;
//取相反数, j的质因数可能有多个，奇数个就是-1
}
}
return ;
}
int main() {
return 0;
}
数论函数（算术函数）
定义域在正整数上的函数
我们总的来说分为两类：加性函数和积性函数
加性函数
如果\(\gcd (a,b)=1\)，那么\(f(a+b)=f(a)+f(b)\)
完全加性函数:\(a,b\)不一定互质
积性函数
\(a,b\)互质且\(f(1)=1\)，\((f*g)(n)=f(n)*g(n)\)
完全积性函数:\(a,b\)不一定互质
狄利克雷卷积
形式
形式1 \((f*g)(n)=\sum\limits_{xy=n} f(x)\times g(y)\)
形式2 \((f*g)(n)=\sum\limits_{d|n} f(d)\times g(\frac{n}{d})\)
性质
性质一
交换律，结合律，分配律
性质二
普及一个概念：单位函数
\[\epsilon(n)= \begin{cases} 1,n=1\\ 0,n>1 \end{cases} \]我们就有
\[(f*\epsilon)(n)=\sum\limits_{d|n} \epsilon(d)\times f(\frac{n}{d})=f(n) \]考虑\(d=1\)时
性质三
若\(f,g\)都是积性函数
那么\((f*g)(n)\)也是积性函数
证明：
\[(f*g)(1)=f(1)g(1)=1 \]设\(a,b\)互质
\[(f*g)(a)=\sum\limits_{d|a} f(d)\times g(\frac{a}{d})...(1) \]\[(f*g)(b)=\sum\limits_{d|b} f(d)\times g(\frac{b}{d})...(2) \]\[(f*g)(ab)=\sum\limits_{d|ab} f(d)\times g(\frac{ab}{d})...(3) \]\((1)*(2)\)得
\[\sum\limits_{d1|a} f(d1)\times g(\frac{a}{d1}) \times \sum\limits_{d2|b} f(d2)\times g(\frac{b}{d2}) \]整理得（乘法原理）
\[\sum\limits_{d1|a,d2|b} f(d1) * g(\frac{a}{d1})\times f(d2) * g(\frac{b}{d2}) \]所以有
\[\sum\limits_{d1|a,d2|b} f(d1\times d2) * g(\frac{ab}{d1\times d2})\\ =\sum\limits_{d|a b} f(d) * g(\frac{ab}{d}) \]得到\((3)\)式
性质四
关于除数函数与幂函数的小结论（有关常函数）
\[(f*I)(n)=\sum\limits_{d|n} f(d) \times I(\frac{n}{d})=\sum\limits_{d|n} f(d) \]推论
\[(ID_k*I)(n)=\sum\limits_{d|n} ID_k(d)=\sum\limits_(n) \]除数函数和幂函数可以相互转化
其实这就是一个简单的莫比乌斯反演。
性质五
关于欧拉函数的小结论
\[(\varphi * I)(n)=\sum\limits_{d|n} \varphi(d) \]当\(p\)为质数且\(d=p^m\)时
\[\sum\limits_{d|n} \varphi(d)=\varphi(1)+\sum\limits_{i=1}^{m} \varphi(p^i)\\ =1+\sum\limits_{i=1}^{m}(p^i-p^{i-1})=1+p^m-p^0=p^m=d \]综上，\(p\)为质数时，\((\varphi *I)(p^m)=p^m\)
进一步推广得到\((\varphi *I)(n)=n\)
即\(\varphi * I=ID\)
性质六
莫比乌斯函数得小结论
\[(\mu * ID)(n)=\varphi(n) \]证明很短
\[\mu * ID = \mu * (\varphi * I) = \mu * I * \varphi = \epsilon * \varphi = \varphi \]还有\((\mu * I)(n)=\epsilon(n)\)
性质七
\[\mu * I=\varepsilon\\ =\sum\limits_{d|n} \mu(d)=\sum\limits_{i=0}^{k} (-1)^k C(k,i)\\ =\sum\limits_{i=0}^{k} (1)^{k-i} (-1)^k C(k,i)\]这不是二项式定理吗？简化为
\[(1-1)^k \]观察一下发现就是单位函数的定义了
常用积性函数
单位函数
\[\epsilon(n)= \begin{cases} 1,n=1\\ 0,n>1 \end{cases} \]是完全积性函数
幂函数
\[ID_k(n)=n^k \]特别的，当\(k=1\)时，\(ID_1(n)=n\)；\(k=0\)时，\(ID_0(n)=1\)
是完全积性函数
除数函数
\[\sigma_k(n)=\sum\limits_{d|n}d^k \]当\(k=1\)时，\(\sigma_1(n)=\sum\limits_{d|n}d^k\)
叫做约数和函数
当\(k=0\)时，\(\sigma_0(n)=\sum\limits_{d|n}1\)
叫做约数个数函数
莫比乌斯函数
这个不用讲了吧。
欧拉函数
参见
常数函数
\[I(n)=1 \]莫比乌斯反演公式
终于进入正题
\[g(n)=\sum\limits_{d|n} f(d) \]等价于
\[f(n)=\sum\limits_{d|n} \mu(d) g(\frac{n}{d}) \]用更简单得形式为
\(f*I=g\)等价于\(f=g*\mu\)
拿简单的形式来证明
\[f*I=g\\ f*(I*\mu)=g*\mu\\ f*\epsilon=g*\mu\\ f=g*\mu \]做题前的小补充
整除分块
一个小例题
给定一个整数\(n\in [1,10^9]\)
\[\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor \]我们将他们按照\(\lfloor\frac{n}{i}\rfloor\)来分成一个一个块，假设这一个块的左右边界分别是\(L,R\)
则有
\[\left\lfloor\frac{n}{L}\right\rfloor=\left\lfloor\frac{n}{R}\right\rfloor\\ \left\lfloor\frac{n}{L}\right\rfloor\leq \frac{n}{R}\\ \frac{1}{\left\lfloor\frac{n}{L}\right\rfloor} \geq \frac{R}{n}\\ R\leq \left\lfloor\frac{n}{\left\lfloor\frac{n}{L}\right\rfloor}\right\rfloor\]又因为\(R\in Z\)
\[R=\left\lfloor\frac{n}{\left\lfloor\frac{n}{L}\right\rfloor}\right\rfloor \]真例题这里
可以化简为以上的形式，就不分析了（考虑贡献）
代码
#include
#define int long long
using namespace std;
int n, ans;
signed main() {
cin >> n;
for (int l = 1, r; l <= n; l = r + 1) {
r = (n / (n / l));
ans += (r - l + 1) * (n / l);
}
cout << ans;
return 0;
}
小小小扩展这里
我们实际上求的是
\[\sum\limits_{i=1}^n i*\lfloor\frac{n}{i}\rfloor \]对于每一个块单独分析一波，就好了（高斯求和公式）
Code
#include
#define int long long
using namespace std;
int x, y;
int sum(int x) {
int ans = 0;
for (int l = 1, r; l <= x; l = r + 1) {
r = (x / (x / l));
ans += (r - l + 1) * (x / l) * (l + r) / 2;
}
return ans;
}
signed main() {
cin >> x >> y;
cout << sum(y) - sum(x - 1);
return 0;
}
再来一个补充这里
莫比乌斯反演的应用
一.关于\(\gcd\)
\[(\gcd(i,j)==1)=\sum\limits_{d|\gcd(i,j)} \mu(d) \]证明
\[\mu * I=\epsilon\\ \sum\limits_{d|n}\mu(d)=\epsilon=(n==1)\]将\(n=\gcd(i,j)\)带入即可得到结论
二.还是关于\(\gcd\)
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} (\gcd(i,j)==k)\Rightarrow \sum\limits_{i=1}^{\frac{n}{k}}\sum\limits_{j=1}^{\frac{n}{k}} (\gcd(i,j)==1) \]例题：求\(1\leq x\leq n, 1\leq y\leq m, \gcd(x,y)=1\)的数量
\[\Rightarrow \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d|\gcd}^{min\{n,m\}} \]太难搞，改为枚举\(\gcd\)
\[\sum\limits_{d=1}^{min\{n,m\}} \sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{m/d}\mu(d)\\ \Rightarrow \sum\limits_{d=1}^{min\{n,m\}}\mu(d)\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{m/d}\\ \Rightarrow \sum\limits_{d=1}^{min\{n,m\}}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor \left\lfloor\frac{m}{d}\right\rfloor\]一个整除分块（二维）就做好了
杜教筛
应用场景：求积性函数\(f(n)\)的前缀和，即
\[\sum\limits_{i=1}^{n} f(i) \]我们设
\[S(n)=\sum\limits_{i=1}^{n} f(i) \]我们构造另一个积性函数\(g(n)\)，那么有\((f*g)(n)\)
\[\sum\limits_{i=1}^{n} (f*g)(i)=\sum\limits_{i=1}^{n}\sum\limits_{xy=1}f(x)g(y)\\ \Rightarrow \sum\limits_{y=1}^{n}\sum\limits_{x=1}^{\lfloor\frac{n}{y}\rfloor}f(x)g(y)\\ \Rightarrow \sum\limits_{y=1}^{n} g(y) \sum\limits_{x=1}^{\lfloor\frac{n}{y}\rfloor}=\sum\limits_{y=1}^{n} g(y) S(\lfloor\frac{n}{y}\rfloor)\\ \Rightarrow g(1)S(n)+\sum\limits_{y=2}{n}g(y)S(\lfloor\frac{n}{y}\rfloor)\]移项可得
\[g(1)S(n)=\sum\limits_{i=1}^{n}(f*g)(i)-\sum\limits_{y=2}^{n}g(y)S(\lfloor\frac{n}{y}\rfloor) \]这里我们令\(f=\mu\)，因为\(\mu*I=\epsilon\)
代入得
这样我们就得到了一个递推式，如果我们纯递归的话时间复杂度为\(O(n^{\frac{3}{4}})\)
我们有一个小技巧，先用线性筛筛出前\(\frac{2}{3}n\)个\(\mu\)，再来递推，就可以优化到\(O(n^{\frac{2}{3}})\)
很神奇吧，时间复杂度我不会证明（菜）
例题
P3455 [POI2007]ZAP-Queries
我们看一下这道题要我们求的式子
\[\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}[\gcd(i,j)=d] \]根据上面的定理可以得到
\[\sum\limits_{i=1}^{\left\lfloor a/d\right\rfloor}\sum\limits_{j=1}^{\left\lfloor b/d\right\rfloor}[\gcd(i,j)=1] \]令\(x=a/d,y=b/d\)，反演得到
\[\sum\limits_{d=1}^{min\{x,y\}}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor \left\lfloor\frac{m}{d}\right\rfloor \]注意这一个式子中的\(d\)不是题目中的
我们先预处理出来莫比乌斯函数的前缀和，然后用一个整出分块就做完了，还是很模板的
#include
#define int long long
using namespace std;
const int N = 5e4 + 10;
int n, m;
int miu[N], sum[N];
bool vis[N];
vector pri;
void init(int n) {
for (int i = 1; i <= n; i++) {
miu[i] = 1;
vis[i]= false;
}
for (int i = 2; i <= n; i++) {
if(vis[i] == true)
continue;
miu[i] = -1;
//质数自己 ,-1
pri.push_back(i);
for (int j = 2*i; j <= n; j+=i) {
vis[j] = true;
if(j % (i*i) == 0)
miu[j] = 0; else
miu[j] *= -1;
//取相反数, j的质因数可能有多个，奇数个就是-1
}
}
for (int i = 1; i<= n; i ++)
sum[i] = sum[i - 1] + miu[i];
return ;
}
int Get(int n, int m) {
int ans = 0;
for (int l = 1, r; l <= min(n, m); l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans += (n / l) * (m / l) * (sum[r] - sum[l - 1]);
}
// cout << ans << endl;
return ans;
}
signed main() {
ios::sync_with_stdio(false);
init(50000);
int T;
cin >> T;
while(T --) {
int ans = 0, d = 0;
cin >> n >> m >> d;
cout << Get(n / d, m / d) << "\n";
}
return 0;
}
愉快的做出来第一道莫反题目