sopj 7001 （莫比乌斯反演）

本文主要是介绍sopj 7001 （莫比乌斯反演），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://vjudge.net/contest/238531#problem/B
题意：给一个$N\times N\times N$的坐标系，从源点 (0,0,0)发出的光线，最多能照到几个坐标点
这道题用的是莫比乌斯反演的倍数那种形式
也就是

$$F(n)=\sum_{n|d}f(d)$$
$$f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)$$

这种题一般都是直接求 $f(n)$ 不好求，但是关于 $n$ 的倍数 $F(n)$ 是好得到的，然后再反演就能得到 $f(n)$

而且是分情况的，拿 $N=3$ 举例：
①这三个点都不为 $0$（点都不在坐标面上）
$f(n)$ 表示 $gcd(x,y,z)=n$的点有多少个
$F(n)$ 表示 $gcd(x,y,z)=n$的倍数的点有多少个
最后要的结果是 $gcd(x,y,z)=1$，所以求的就是 $f(1)$
$f(1)=\sum_{1|d}\mu(\frac{d}{1})F(d)$
$=\mu(1)F(1)+\mu(2)F(2)+\mu(3)F(3)$

而：
$F(1)=\frac{N}{1}*\frac{N}{1}*\frac{N}{1}=27$
$F(2)=\frac{N}{2}*\frac{N}{2}*\frac{N}{2}=1$
$F(3)=\frac{N}{3}*\frac{N}{3}*\frac{N}{3}=1$

所以$ans1=f(1)=\mu(1)*F(1)+\mu(2)*F(2)+\mu(3)*F(3)=27-1-1=25$

②只有一个点为 $0$ （点在坐标面上，而且有三个坐标面）
$f(n)$ 表示 $gcd(x,y)=n$的点有多少个
$F(n)$ 表示 $gcd(x,y)=n$的倍数的点有多少个

同理，最后要的结果是 $gcd(x,y)=1$，所以求的就是 $f(1)$
$f(1)=\sum_{1|d}\mu(\frac{d}{1})F(d)$
$=\mu(1)F(1)+\mu(2)F(2)+\mu(3)F(3)$

$F(1)=\frac{N}{1}*\frac{N}{1}=9$
$F(2)=\frac{N}{2}*\frac{N}{2}=1$
$F(3)=\frac{N}{3}*\frac{N}{3}=1$

所以$f(1)=\mu(1)*F(1)+\mu(2)*F(2)+\mu(3)*F(3)=9-1-1=7$

而这种有三个坐标面
所以$ans2=3*f(1)=21$

③有两个点都为 $0$ （就是在坐标轴上）
$f(n)$ 表示 $gcd(x)=n$的点有多少个
$F(n)$ 表示 $gcd(x)=n$的倍数的点有多少个

同理，最后要的结果是 $gcd(x)=1$，所以求的就是 $f(1)$
$f(1)=\sum_{1|d}\mu(\frac{d}{1})F(d)$
$=\mu(1)F(1)+\mu(2)F(2)+\mu(3)F(3)$

$F(1)=\frac{N}{1}=3$
$F(2)=\frac{N}{2}=1$
$F(3)=\frac{N}{3}=1$

所以$f(1)=\mu(1)*F(1)+\mu(2)*F(2)+\mu(3)*F(3)=3-1-1=1$

同样，有三个坐标轴
所以$ans3=3*f(1)=3$
其实这种情况一眼就能看出来，但是我想突出这个莫比乌斯的牛逼（真的太牛逼了），于是就演算了一哈
所以$ans=ans1+ans2+ans3=25+21+3=49$

这篇关于sopj 7001 （莫比乌斯反演）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---