莫比乌斯反演

目录

• 一、前言
• 二、讲解
  • 1.莫比乌斯函数
    • (1).定义
    • (2).性质
      • ①
      • ② 一个关系式
      • ③ 积性函数
    • (3).线性筛代码
  • 2.莫比乌斯反演
• 三、练习

一、前言

这是第三遍讲？明明是第一遍学！

为了不让博客过于冗长，部分证明已被省略，详见 ( exttt{PPT})

二、讲解

保留节目——自学

1.莫比乌斯函数

(1).定义

我们莫比乌斯函数为 (mu(n)(nin N^*)) ，定义如下：

① (mu(1)=1)

② 如果(n=prod_{i=1}^kp_i) 且(p_i)互不相同，则 (mu(n)=(-1)^k)

③ 其他情况下 (mu(n)=0)

(2).性质

①

对于任意正整数 (n) 有：

[sum_{d|n}mu(d)=egin{cases} 1 (n=1)\ 0 (n>1) end{cases}]

② 一个关系式

[sum_{d|n}dfrac{mu(d)}{d}=dfrac{phi(n)}{n} ]

( exttt{Hint}) : 考虑移项 (n) 证明

③ 积性函数

(3).线性筛代码

int mu[MAXN],prime[MAXN],pn;
bool vis[MAXN];
void sieve(int x)
{
	smu[1] = mu[1] = 1;
	for(int i = 2;i <= x;++ i)
	{
		if(!vis[i]) prime[++pn] = i,mu[i] = -1;
		for(int j = 1;j <= pn && i * prime[j] <= x;++ j)
		{
			vis[i * prime[j]] = 1;
			if(i % prime[j] == 0) break;
			mu[i * prime[j]] = -mu[i];
		}
	}
}

2.莫比乌斯反演

其实就是一个公式的变形：

[F(n)=sum_{d|n}f(d) ]

[Rightarrow f(n)=sum_{d|n}mu(d)F(dfrac{n}{d}) ]

三、练习

1.[HAOI2011]Problem b(洛谷) 题解

2.YY的GCD(洛谷) 题解

3.Crash的数字表格(洛谷) 题解