自变量互质的前缀和函数分析

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

有这样一类问题，他们的形式常常是这个样子

$$\begin{array}{r}\sum _{i=1}^{n}f(i)[gcd(i,j)=1]\end{array}$$

我们来对他进行变形

$$\begin{array}{rl}& \sum _{i=1}^{n}f(i)[gcd(i,j)=1]\\ =& \sum _{i=1}^{n}f(i)e(gcd(i,j))\\ =& \sum _{i=1}^{n}f(i)(\mu \ast 1)(gcd(i,j)\\ =& \sum _{i=1}^{n}f(i)\sum _{d|gcd(i,j)}\mu (d)\\ =& \sum _{i=1}^{n}f(i)\sum _{d|i,d|j}\mu (d)\\ =& \sum _{d|j}\mu (d)\sum _{d|i,1<=i<=n}f(i)\\ =& \sum _{d|j}\mu (d)\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }f(i\ast d)\end{array}$$

如果$f(i)=1$ 则

$$\begin{array}{r}\sum _{i=1}^n[gcd(i,j)=1]=\sum _{d|j}\mu (d)\lfloor \frac{n}{d}\rfloor \end{array}$$ ## 更加特殊的 如果$j=n$ 则

$$\begin{array}{r}\sum _{i=1}^n[gcd(i,n)=1]=\sum _{d|j}\mu (d)\frac{n}{d}=(\mu \ast id)(n)=\varphi (n)\end{array}$$

如果$f(i)=i$ 则

$$\begin{array}{rl}& \sum _{i=1}^{n}i[gcd(i,j)=1]\\ =& \sum _{d|j}\mu (d)\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }i\ast d\\ =& \sum _{d|j}\mu (d)d\frac{\lfloor \frac{n}{d}\rfloor (\lfloor \frac{n}{d}\rfloor +1)}{2}\end{array}$$ ## 更加特殊的 如果$j=n$ 则

$$\begin{array}{rl}& \sum _{i=1}^{n}i[gcd(i,n)=1]\\ =& \sum _{d|n}\mu (d)d\frac{\frac{n}{d}(\frac{n}{d}+1)}{2}\\ =& \frac{n}{2}\sum _{d|n}\mu (d)(\frac{n}{d}+1)\\ =& \frac{n}{2}(\sum _{d|n}\mu (d)\frac{n}{d}+\sum _{d|n}\mu (d))\\ =& \frac{n}{2}(\varphi (n)+e(n))\end{array}$$

总结

$ $$\begin{array}{rl}& \sum _{i=1}^{n}f(i)[gcd(i,j)=1]=\sum _{d|j}\mu (d)\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }f(i\ast d)\\ & \sum _{i=1}^n[gcd(i,j)=1]=\sum _{d|j}\mu (d)\lfloor \frac{n}{d}\rfloor \\ & \sum _{i=1}^n[gcd(i,n)=1]=\varphi (n)\\ & \sum _{i=1}^{n}i[gcd(i,j)=1]=\sum _{d|j}\mu (d)d\frac{\lfloor \frac{n}{d}\rfloor (\lfloor \frac{n}{d}\rfloor +1)}{2}\\ & \sum _{i=1}^{n}i[gcd(i,n)=1]=\frac{n}{2}(\varphi (n)+e(n))\end{array}$$

$