莫比乌斯反演
莫比乌斯函数
定义
将 \(n\) 质因数分解
\[n = \prod_{i=1}^{k} p_i^{\alpha _i} \]则
\[\mu (n)= \left\{\begin{matrix} 1, &n=1 \\ 0, & \exists \alpha _i>1\\ (-1)^k, & \forall \alpha _i=1 \end{matrix}\right.\]性质
- 积性函数.
- \(s(n) = \sum_{d|n} \mu (d) =\left\{\begin{matrix} 1, & n=1\\ 0, & n≠1 \end{matrix}\right.\)
线性筛
code
int primes[N], cnt, mu[N];
bool st[N];
void init()
{
mu[1] = 1;
for (int i = 2; i < N; i ++ )
{
if (!st[i]) primes[ ++ cnt] = i, mu[i] = -1;
for (int j = 1; j <= cnt && primes[j] * i < N; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
mu[primes[j] * i] = -mu[i];
}
}
}
莫比乌斯反演
对于一些函数 \(f(n)\)，如果很难直接求出它的值，而容易求出其倍数和或约数和 \(g(n)\)，那么可以通过莫比乌斯反演简化运算，求得 \(f(n)\) 的值.
定义
-
形式一：
若 \(g(n)=\sum_{d|n}f(d)\), 则 \(f(n) = \sum _{d|n} \mu (d) g(\frac{n}{d})\).
-
形式二：
若 \(g(n)= \sum _{n|d} f(d)\), 则 \(f(n) = \sum_{n|d} \mu (\frac{d}{n})g(d)\).