Möbius函数

定义

$$\mu(n)=\begin{cases}
1 & \text{ if } n=1 \\
(-1)^r & \text{ if } n=p_1p_2 \cdots p_r \text{, where the } p_i \text{ are distinct primes} \\
0 & \text{ otherwise}
\end{cases}$$

性质

  • $sum_{d|n}{\mu(d)}=[n=1]=e(n)$
  • $\sum_{d|n}{\frac{\mu(d)}{d}}=\frac{\phi(n)}{n}$

定义求Möbius函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Mobius_mu(int n){
int res=1;
for(int i=2;i*i<=n;++tot){
int cnt=0;
while(n%i==0){
res=-res;
n/=i;
if(++cnt>=2) retrun 0;
}
if(p<=1) break;
}
if(n>1) res=-res;
return res;
}

线性筛求Möbius函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Mobius(){
memset(vis,0,sizeof vis);
int tot=0;mu[1]=1;
for(int i=0;i<n;++i){
if(!vis[i]){
primes[tot++]=i;
mu[i]=-1;
}
for(int j=0;j<tot;++j){
int t=i*primes[j];
if(t>maxn) break;
vis[t]=1;
if(i%primes[t]==0){ //某质因子幂大于1
mu[t]=0;
break;
}else mu[t]=-mu[i];
}
}

Möbius反演(Möbius Inversion)

定义

  • 设$f$是一个数论函数, 然后$F$是$f$的和型函数, 即$$F(n)=\sum_{d|n}{f(d)}$$

  • 那么对于所有的正整数$n$, 都有下面式子成立$$f(n)=\sum_{d|n}{\mu(d)F(n/d)}$$

  • 即已知函数$F(n)$,我们利用公式求出$f(n)$

常用函数

$f(n)=\sum_{d \mid n}{\mu(d)F(n/d)}$ $F(n)=\sum_{d \mid n}{f(d)}$
$\mu(n)d(n)$ $\mu(n)$
$\mu(n)$ $e(n)$
$e(n)$ 1
1 $d(n)$
$\phi(n)\displaystyle\prod_{p \mid n}{\frac{p-2}{p-1}}$ $\phi(n)$
$\phi(n)$ $id(n)=n$
$J_k(n)$ $id_k(n)=n^k$
$id(n)=n$ $\sigma(n)$
$id_k(n)=n^k$ $\sigma_k(n)$
$\frac{1}{n}\displaystyle\prod_{p \mid n}{1-p}$ $\frac{1}{n}$
$-\mu(n)\ln(n)$ $\Lambda(n)$
$\Lambda(n)$ $\ln(n)$

常用函数定义

  • $e(n)=[n=1]$, 也有一种写法是$\iota(n)$ (单位函数)

  • $id(n) = n$ (恒等函数)

  • $d(n) = \sum_{d|n}{1}$ (number-of-divisors function)

  • $\sigma(n)=\sum_{d|n}{d}$ (sum-of-divisors function)

  • $\sigma_k(n)=\sum_{d|n}{d^k}$

  • $\phi(n) = \sum_{(d,n)=1}{1}$ (Euler’s totient function)

  • $J_k(n)=\sum_{(d,n)=1}{d^k}=n^k\prod_{d|n}(1-\frac{1}{d^k})$ (Jordan’s totient function)

  • $\Lambda (n)=\begin{cases}\ln p & \text{ if } n=p^k \text{ for some prime }p\text{ and integer }k \ge 1 \\
    0 & \text{ otherwise}
    \end{cases}$ (Von Mangoldt function)

题目

例题

例1

给定整数$N, M(1 \le N, M \le 10^7)$, 求$\sum_{i=1}^{N}{\sum_{j=1}^{M}{(i,j)}}$

根据上表 $n = \sum_{d|n}{\phi(d)}$,令$n = (i,j)$
$\begin{align}
\sum_{i=1}^{N}{\sum_{j=1}^{M}{(i,j)}}
& =\sum_{i=1}^{N}{\sum_{j=1}^{M}{\sum_{d|(i,j)}{\phi(d)}}} \\
& =\sum_{d=1}^{min(N,M)}{\phi(d)\sum_{i=1}^{N}{\sum_{j=1}^{M} [d|(i,j)]}} \\
& =\sum_{d=1}^{min(N,M)}{\phi(d)\sum_{i=1}^{N}{[d|i]\sum_{j=1}^{M}[d|j]}} \\
& =\sum_{d=1}^{min(N,M)}{\phi(d) \lfloor \frac{N}{d} \rfloor \lfloor \frac{M}{d} \rfloor} \\
\end{align}$

直接暴力复杂度$O(min(N,M))$
根据分块预处理复杂度为 $O(\sqrt{N} + \sqrt{M})$
具体可以参考下面的 bzoj2301

例2

给定整数$N, M(1 \le N, M \le 10^7)$, 求$\sum_{i=1}^{N}{\sum_{j=1}^{M}{[(i,j)=1]}}$

令$e(n) = [n=1] = \sum_{d|n} \mu(d)$

$\begin{align}
\sum_{i=1}^{N}{\sum_{j=1}^{M}{[(i,j)=1]}}
&=\sum_{i=1}^{N}{\sum_{j=1}^{M}{\sum_{d|(i,j)}{\mu(d)}}} \\
&\dots \\
&=\sum_{d=1}^{min(N,M)}{\mu(d) \lfloor \frac{N}{d} \rfloor \lfloor \frac{M}{d} \rfloor} \\
\end{align}$

与例1同理,且很容易地可以推广到$\sum_{i=1}^{N}{\sum_{j=1}^{M}{[(i,j)=k]}}$
即求$\sum_{d=1}^{min(N/k,M/k)}{\mu(d) \lfloor \frac{N}{kd} \rfloor \lfloor \frac{M}{kd} \rfloor}$

例3

给定整数$N, M(1 \le N, M \le 10^7)$, 求$\sum_{i=1}^{N}{\sum_{j=1}^{M}{\phi((i,j))}}$

用类似于前两题的做法,令$\phi(n) = \sum_{d|n} f(d)$
现在来推导$f(n)$,因为$\phi(n)$是积性函数,设$p$为质数
若已知$f(p)$ 与 $f(p^k)$,则可以用线性筛预处理出所有的$f(n)$
先反演一下,$f(n) = \sum_{d|n}{\mu(d)\phi(n/d)}$

$\begin{align}
f(p)
&= \sum_{d|p}{\mu(d)\phi(p/d)} \\
&= \mu(1)\phi(p) + \mu(p)\phi(1) \\
&= p - 2
\end{align}$

$\begin{align}
f(p^k)
&= \sum_{d|p^k}{\mu(d)\phi(p^k/d)} \\
&= \mu(1)\phi(p^k) + \mu(p)\phi(p^{k-1}) + \dots + \mu(p^k)\phi(1) \\
&= (p^k - p^{k-1}) - (p^{k-1} - p^{k-2}) \\
&= p^{k-2}(p^k-1)^2
\end{align}$

例4

给定整数$N, M(1 \le N, M \le 10^7)$, 求$\sum_{i=1}^{N}{\sum_{j=1}^{M}{lcm(i,j)}}$

$\begin{align}
\sum_{i=1}^{N}{\sum_{j=1}^{M}{lcm(i,j)}}
& =\sum_d \sum_{i=1}^{N}{\sum_{1 \leq j \leq M \text{ and } (a,b) = d}{\frac{ab}{d}}} \\
& =\sum{d \sum_{i=1}^{N/d}\sum_{j=1}^{M/d}{[(a,b)=1]ab}} \\
\text{令}f(n,m) = \sum_{i=1}^{n}\sum_{j=1}^{m}{[(a,b)=1]ab} \\
f(n,m)
&= \sum_{i=1}^n\sum_{j=1}^m{ab\sum_{d|(i,j)}\mu(d)} \\
&= \sum{\mu(d)\lfloor \frac{N}{d} \rfloor \lfloor \frac{M}{d} \rfloor \frac{d(\lfloor \frac{N}{d} \rfloor + 1)}{2} \frac{d(\lfloor \frac{M}{d} \rfloor + 1)}{2}} \\
&= \frac{1}{4}\sum{\mu(d)d^2 \lfloor \frac{N}{d} \rfloor \lfloor \frac{M}{d} \rfloor d(\lfloor \frac{N}{d} \rfloor + 1) d(\lfloor \frac{M}{d} \rfloor + 1)} \\
\text{将} f(n,m) \text{带回原式} \\
\sum_{i=1}^{N}{\sum_{j=1}^{M}{lcm(i,j)}}
&= \frac{1}{4}\sum d \sum_{d’|d}{\mu(d’)d’^2 \lfloor \frac{N/d}{d’} \rfloor \lfloor \frac{M/d}{d’} \rfloor (\lfloor \frac{N/d}{d’} \rfloor + 1) (\lfloor \frac{M/d}{d’} \rfloor + 1)} \\
&= \frac{1}{4} \sum{\lfloor \frac{N}{d} \rfloor \lfloor \frac{M}{d} \rfloor (\lfloor \frac{N}{d} \rfloor + 1) (\lfloor \frac{M}{d} \rfloor + 1) d\sum_{d’|d}{d’\mu(d’)}}
\end{align}$

$\text{令} g(n) = n\sum_{d|n}{d\mu(d)}$,是一个积性函数
$g(p) = p(1 - p)$
$g(p^k) = p^k(1-p)$
突然发现这不就是 $p\phi(p)$ 么…

例5

给定两个数$N,M(1 \le N ,M \le 10^7)$, 其中$1 \le x \le N, 1 \le y \le M$, 求$(x,y)$为质数的$(x,y)$有多少对.

  • 简化版
    $1 \le x,y \le N$
    我们知道$\phi(N/g)$ 表示 $x = 1..N-1$ 中 $(x,N) = g$的个数
    我们枚举质数g,然后预处理出$2\phi(n)$的前缀和$f$
    并且令$f(1) = 1$,表示$gcd(p,p) = p$的情况

  • 方法1
    按照例2,$\sum_{p \in P}\sum_{d=1}^{\min{N/pd,M/pd}}{\mu(d)\lfloor \frac{N}{pd} \rfloor \lfloor \frac{M}{pd}\rfloor}$
    然而复杂度爆炸

  • 方法2
    令$kp = T$,答案就是
    $\sum_{T=1}^{min(N/T,M/T)}{ \lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor \sum_{p|T}\mu(\frac{T}{p})}$
    令$g(T) = \sum_{p|T}\mu(\frac{T}{p})$
    很遗憾$g(T)$不是积性函数,可是$T = kp$,p为质数时,$g(T)$依然可以用线性筛预处理
    $g(kp) = \begin{cases}
    \mu(k) &if \; p|k \\
    \mu(k) - g(k) &if \; p \not{|} k
    \end{cases}$
    这样就可以在求$\mu(n)$的同时求$g(n)$了,式子变成了熟悉的形式:
    $\sum_{T=1}^{min(n/T,m/T)}{ g(T) \lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor }$

题目

bzoj2301

给出q个询问,每次求有多少对$(x,y)$满足
$r \leq x \leq m \,\, , \,\, l \leq y \leq n \,\,\, gcd(x,y)=k$

根据上面的公式
$f(m,n) = \sum_{d=1}^{min(N/k,M/k)}{\mu(d) \lfloor \frac{N}{kd} \rfloor \lfloor \frac{M}{kd} \rfloor}$

再根据容斥原理
$ans = f(m,n)-f(l-1,m)-f(r-1,n)+f(l-1,r-1)$

1
2
3
4
5
6
7
8
//先来看暴力求解
LL f(int m,int n,int k){
m/=k;n/=k;
int N=min(m,n);
LL ans=0;
for(int i=1;i<=N;++i) ans+=1LL*mu[i]*(m/i)*(n/i);
return ans;
}

复杂度$O(qmin(m/k,n/k))$肯定超时,下面考虑分块

连续的k项可能有$a/x = a/(x+1) = \dots = a/(x+k-1)$
所以我们预处理$\mu$的前缀和,然后每次计算$a/x = \dots = a/(x+k-1)$k项的答案

那如何求k呢?
对于当前点x,最远可以延伸到$min(m/(m/x),n/(n/x))$

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=2;i<=maxn;++i) mu[i]+=mu[i-1];
LL f(int m,int n,int k){
m/=k;n/=k;
int N=min(m,n),l=1,r;
LL ans=0;
while(l<=N){
r=min(min(m/(m/l)),n/(n/l))),N);
ans+=1LL*(mu[r]-mu[l-1])*(m/l)*(n/l);
l = r+1;
}
return ans;
}

复杂度为$O(q(\sqrt{m/k} + \sqrt{n/k}))$

ACdream 1114

给出d和n个数,在这n个数中选取两个数$(x_i,x_j) \,\, (i<j) \text{使} gcd(x_i,x_j)=k$,求有多少种组合。

根据例2的公式可以得出

$\begin{align}
\sum_{i=1}^{N}{\sum_{j=1}^{N}{[(x_i,x_j)=k]}}
&=\sum_{i=1}^{N}{\sum_{j=1}^{N}{\sum_{kd|(i,j)}{\mu(d)}}} \\
&\dots \\
&=\sum {\mu(d) cnt_{kd}(cnt_{kd} - 1)/2 } \\
\end{align}$

我们可以$O(nlogn)$预处理出所有$cnt_d$,即因子含d的数的个数(保证$k|x$,将每个$x$除以k)

bzoj2154

即例4

bzoj2820

即例5

参考