莫比乌斯反演笔记

2020-08-05

莫比乌斯反演有什么作用？
对于一些函数 $f(n)$，如果我们很难直接求出它的值，而容易求出倍数和或约数和 $F(n)$，那么我们可以通过莫比乌斯反演来求得 $f(n)$ 的值。

引子

首先来看一个函数：$$F(n) = \sum_{d|n}f(d)$$
根据F函数的定义，可以得到：
$$F(1) = f(1)$$ $$F(2) = f(1) + f(2)$$ $$F(3) = f(1) + f(3)$$ $$F(4) = f(1) + f(2) + f(4)$$ $$F(5) = f(1) + f(5)$$ $$F(6) = f(1) + f(2) + f(3) + f(6)$$

如果我们已知 $F(n)$ 我们可以通过反推求出 $f(n)$：
$$f(1) = F(1)$$ $$f(2) = F(2) - F(1)$$ $$f(3) = F(3) - F(1)$$ $$f(4) = F(4) - F(2)$$ $$f(5) = F(5) - F(1)$$ $$f(6) = F(6) - F(3) - F(2) + F(1)$$

在这个反推的过程中存在一些规律，总结起来公式如下：$$F(n) = \sum_{d|n}f(d) –>f(n) = \sum_{d|n}u(d)F(\frac{n}{d})$$

其中的$u(d)$就是莫比乌斯函数。

莫比乌斯函数$u(d)$

函数定义：
$$ u(d) = \begin{cases}
1 & (d=1)\
(-1)^k & (d = p_1p_2p_3 \cdots p_k) \
0 & (others)
\end{cases}$$

函数性质

对于任意正整数n有
$$\sum_{d|n}u(d) = \begin{cases}
1 & (n = 1)\
0 & (n > 1)
\end{cases}$$

证明：

若n = 1，那么显然成立；
若n ≠ 1，那么n一定可以分解得到 $n = p_1^{a1} \cdots p_k^{ak}$
因此在n的所有因子中，当且仅当该因子的所有质因子次数均为1时u值不为零。其中，质因子个数为r个的因子有$C_k^r$个。
那么显然 $$\sum_{d|n}u(d) = C_k^0 - C_k^1 + C_k^2 + \cdots + (-1)^kC_k^k = \sum^k_{i=0} (-1)^iC_k^i$$
又因为二项式定理 $$(x+y)^n = \sum^n_{i=0}C^i_nx^iy^{n-i}$$
所以令$x = -1, y = 1$，代入，证明完毕。
_
1. 积性函数
数论中积性函数的定义：
设 $f(n)$ 为一个定义在 $N^+$ 集合上的函数，如果对于任意的 $(x, y)=1$ 有 $f(xy)=f(x)f(y)$，则称 $f(n)$ 为一个 *积性函数；
若对于任意x和y均有 $f(xy)=f(x)f(y)$ ，则称 $f(n)$ 为一个 *完全积性函数。
积性函数的性质
$f(1) = 1$；
积性函数的前缀和也是积性函数；
_
1. (不重要)对任意正整数n有：$$\sum_{d|n} \frac{u(d)}{d} = \frac{\phi(n)}{n}$$
证明：
只需要令$F(n) = n,f(n) = \phi (n)$代入莫比乌斯反演公式即可。

Mobius函数代码
由于莫比乌斯函数是积性函数，因此可以通过线性筛来求出莫比乌斯函数的值

const int N = 100000;
bool check[N+10];
int prime[N+10];
int mu[N+10];
void Moblus() {
   memset(check,false,sizeof(check));
   mu[1] = 1;
   int tot = 0;
   for(int i = 2; i <= N; i++) {
      if( !check[i] ) {
         prime[tot++] = i;
         mu[i] = -1;
      }
      for(int j = 0; j < tot; j++) {
         if(i * prime[j] > N) break;
         check[i * prime[j]] = true;
         //改变质因子系数进而得到函数值
         if( i % prime[j] == 0)  {
            mu[i * prime[j]] = 0;
            break;
         } else {
            mu[i * prime[j]] = -mu[i];
         }
      }
   }
}

莫比乌斯反演

形式一
$$F(n) = \sum_{d|n}f(d) –>f(n) = \sum_{d|n}u(d)F(\frac{n}{d})$$

证明：
对原式做数论变换：
$$\sum_{d|n}u(d)F(\frac{n}{d}) = \sum_{d|n}u(d)\sum_{d|\frac{n}{k}}f(k) = \sum_{k|n}f(k)\sum_{d|\frac{n}{k}}u(d)$$
根据莫比乌斯函数性质，有
$$\sum_{d|n}u(d) = \begin{cases}
1 & (n = 1)\
0 & (n > 1)
\end{cases}$$
因此当且仅当$\frac{n}{k} = 1$时，即n=k时，$\sum_{d|\frac{n}{k}}u(d)=1$，否则为0.
所以$$\sum_{k|n}f(k)\sum_{d|\frac{n}{k}}u(d) = f(n)$$

形式二
$$F(n) = \sum_{n|d}f(d) –>f(n) = \sum_{n|d}u(\frac{d}{n})F(d)$$

证明
与形式一同理
$$\sum_{n|d}u(\frac{d}{n})F(d) = \sum_{k=1}^{+∞}u(k)f(nk) = \sum_{k=1}^{+∞}u(k)\sum_{nk|t}f(t) = \sum_{n|t}f(t)\sum_{k|\frac{t}{n}}u(k)$$
同理当且仅当$\frac{t}{n} = 1$时，即t=n时，$\sum_{k|\frac{t}{n}}u(k)=1$，否则为0.
最终得到
$$\sum_{n|t}f(t)\sum_{k|\frac{t}{n}}u(k) = f(n)$$
证毕。
卷积证明自己了解。

应用

BZOJ2301(所有教程都有的经典例题)

题意：
对于给出的 n 个询问，每次求有多少个数对 (x, y)，满足 a <= x <= b, c <= y <= d，且gcd(x, y) = k，gcd(x, y) 函数为 x 和 y 的最大公约数。1 <= n <= 50000, 1 <= a <= b <=50000, 1 <= c <= d <= 50000, 1 <= k <= 50000

思路：
首先利用容斥原理将一个询问拆分成四个，每次询问有多少个数对(x,y)满足1<=x<=n,1<=y<=m且gcd(x,y)=k，这个问题等价于询问有多少个数对(x,y)满足1<=x<=floor(n/k),1<=y<=floor(m/k)且x与y互质。
由于之前的结论，我们可以令f(i)为1<=x<=n,1<=y<=m且gcd(x,y)=i的数对(x,y)的个数，F(i)为1<=x<=n,1<=y<=m且gcd(x,y)为i的倍数的数对(x,y)的个数
那么显然 $F(i) = \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor$
代入到莫比乌斯反演中，得到$f(i) = \sum_{i|d}u(\frac{d}{i})F(d) = \sum_{i|d}u(\frac{d}{i})\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor$ 然后枚举每一个k的倍数即可。
优化：$\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor$都最多有$2\sqrt{n}和2\sqrt{m}$个值，因此枚举这$2(\sqrt{n} + \sqrt{m})$个取值，对莫比乌斯函数维护前缀和，即可在$O(\sqrt{n})$得出解。

代码来自kuangbin

const int MAXN = 100000;
bool check[MAXN+10];
int prime[MAXN+10];
int mu[MAXN+10];
void Moblus() {
   memset(check,false,sizeof(check));
   mu[1] = 1;
   int tot = 0;
   for(int i = 2; i <= N; i++) {
      if( !check[i] ) {
         prime[tot++] = i;
         mu[i] = -1;
      }
      for(int j = 0; j < tot; j++) {
         if(i * prime[j] > N) break;
         check[i * prime[j]] = true;
         //改变质因子系数进而得到函数值
         if( i % prime[j] == 0)  {
            mu[i * prime[j]] = 0;
            break;
         } else {
            mu[i * prime[j]] = -mu[i];
         }
      }
   }
}
int sum[MAXN+10];
//找 [1,n],[1,m] 内互质的数的对数
long long solve(int n,int m) {
   long long ans = 0;
   if(n > m) swap(n,m);
   for(int i = 1, la = 0; i <= n; i = la+1) {
      la = min(n/(n/i), m/(m/i));
      ans += (long long)(sum[la] - sum[i-1])*(n/i)*(m/i);
   }
   return ans;
}
int main() {
   Moblus();
   sum[0] = 0;
   for(int i = 1;i <= MAXN;i++)
      sum[i] = sum[i-1] + mu[i];
   int a,b,c,d,k;
   int T;
   scanf("%d",&T);
   while(T--){
      scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
      long long ans = solve(b/k,d/k) - solve((a-1)/k,d/k) - solve(b/k,(c-1)/k) + solve((a-1)/k,(c-1)/k);
      printf("%lld\n",ans);
   }
   return 0;
}