|
自己推了一下莫比乌斯反演
这种公式类的还是需要自己推过，但以免遗忘，特写此文
莫比乌斯函数求法(线性筛)：
void init(){
mu[1] = 1;
for (int i=2;i<maxm;++i){
if(!st[i]) prime[cnt++] = i,mu[i] = -1;
for(int j = 0;prime[j] * i<maxm;++j){
st[prime[j]*i] = true;
if (i%prime[j] == 0)break;
mu[prime[j]*i] = -mu[i];
}
}
for(int i=1;i<maxm;++i) sum[i] = sum[i-1] +mu[i];
}
当满足
F
(
n
)
F(n)
F(n)
=
=
=
∑
d
∣
n
f
(
d
)
\sum_{d|n}f(d)
∑d∣n?f(d)时
莫比乌斯反演公式：
f
(
n
)
f(n)
f(n)
=
=
=
∑
d
∣
n
d
(
n
)
F
(
n
/
d
)
\sum_{d|n}d(n)F(n/d)
∑d∣n?d(n)F(n/d)
将
F
(
n
/
d
)
F(n/d)
F(n/d)用原公式代替得：
∑
d
∣
n
d
(
n
)
F
(
n
/
d
)
\sum_{d|n}d(n)F(n/d)
∑d∣n?d(n)F(n/d)
=
=
=
∑
d
∣
n
u
(
d
)
\sum_{d|n}u(d)
∑d∣n?u(d)
∑
k
∣
n
/
d
f
(
k
)
\sum_{k|n/d}f(k)
∑k∣n/d?f(k)
由于
k
k
k和
d
d
d都是
n
n
n的因子(这个可以自己代个常数n，一目了然)：
∑
d
∣
n
d
(
n
)
F
(
n
/
d
)
\sum_{d|n}d(n)F(n/d)
∑d∣n?d(n)F(n/d)
=
=
=
∑
k
/
n
f
(
k
)
\sum_{k/n}f(k)
∑k/n?f(k)
∑
d
∣
n
/
k
u
(
d
)
\sum_{d|n/k}u(d)
∑d∣n/k?u(d)
最后由于莫比乌斯函数的性质，只有当
n
/
k
=
1
n/k=1
n/k=1时
∑
d
∣
n
/
k
u
(
d
)
\sum_{d|n/k}u(d)
∑d∣n/k?u(d) 才为1，其他都为0，所以
n
=
k
n=k
n=k，
∑
d
∣
n
d
(
n
)
F
(
n
/
d
)
\sum_{d|n}d(n)F(n/d)
∑d∣n?d(n)F(n/d)
=
=
=
∑
1
f
(
n
)
\sum_{1}f(n)
∑1?f(n)
=
=
=
f
(
n
)
f(n)
f(n)
|