sopj 7001 （莫比乌斯反演）

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

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

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

而：
F(1)=N1∗N1∗N1=27 $F\left(1\right)=\frac{N}{1}\ast \frac{N}{1}\ast \frac{N}{1}=27$
F(2)=N2∗N2∗N2=1 $F\left(2\right)=\frac{N}{2}\ast \frac{N}{2}\ast \frac{N}{2}=1$
F(3)=N3∗N3∗N3=1 $F\left(3\right)=\frac{N}{3}\ast \frac{N}{3}\ast \frac{N}{3}=1$

所以 ans1=f(1)=μ(1)∗F(1)+μ(2)∗F(2)+μ(3)∗F(3)=27−1−1=25 $ans1=f\left(1\right)=\mu \left(1\right)\ast F\left(1\right)+\mu \left(2\right)\ast F\left(2\right)+\mu \left(3\right)\ast F\left(3\right)=27-1-1=25$

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

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

F(1)=N1∗N1=9 $F\left(1\right)=\frac{N}{1}\ast \frac{N}{1}=9$
F(2)=N2∗N2=1 $F\left(2\right)=\frac{N}{2}\ast \frac{N}{2}=1$
F(3)=N3∗N3=1 $F\left(3\right)=\frac{N}{3}\ast \frac{N}{3}=1$

所以 f(1)=μ(1)∗F(1)+μ(2)∗F(2)+μ(3)∗F(3)=9−1−1=7 $f\left(1\right)=\mu \left(1\right)\ast F\left(1\right)+\mu \left(2\right)\ast F\left(2\right)+\mu \left(3\right)\ast F\left(3\right)=9-1-1=7$

而这种有三个坐标面
所以 ans2=3∗f(1)=21 $ans2=3\ast f\left(1\right)=21$

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

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

F(1)=N1=3 $F\left(1\right)=\frac{N}{1}=3$
F(2)=N2=1 $F\left(2\right)=\frac{N}{2}=1$
F(3)=N3=1 $F\left(3\right)=\frac{N}{3}=1$

所以 f(1)=μ(1)∗F(1)+μ(2)∗F(2)+μ(3)∗F(3)=3−1−1=1 $f\left(1\right)=\mu \left(1\right)\ast F\left(1\right)+\mu \left(2\right)\ast F\left(2\right)+\mu \left(3\right)\ast F\left(3\right)=3-1-1=1$

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