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

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

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

$$
\begin{aligned}
\sum_{i=1}^n{f(i)[gcd(i,j)=1]}
\end{aligned}
$$

我们来对他进行变形

$$
\begin{aligned}
&\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)(\mu1)(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(id)}\
\end{aligned}
$$

如果$f(i)=1$ 则

$$
\begin{aligned}
\sum_{i=1}^n{[gcd(i,j)=1]}=\sum_{d|j}{\mu(d)\lfloor\frac{n}{d}\rfloor}\
\end{aligned}
$$

更加特殊的 如果$j=n$ 则

$$
\begin{aligned}
\sum_{i=1}^n{[gcd(i,n)=1]}=\sum_{d|j}{\mu(d)\frac{n}{d}}=(\mu*id)(n)=\phi(n)\
\end{aligned}
$$

如果$f(i)=i$ 则

$$
\begin{aligned}
&\sum_{i=1}^n{i[gcd(i,j)=1]}\
=&\sum_{d|j}{\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}i*d}\
=&\sum_{d|j}{\mu(d)d\frac{\lfloor\frac{n}{d}\rfloor(\lfloor\frac{n}{d}\rfloor+1)}{2}}\
\end{aligned}
$$

更加特殊的 如果$j=n$ 则

$$
\begin{aligned}
&\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}(\phi(n)+e(n))\
\end{aligned}
$$

总结

$
\begin{aligned}
&\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*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]}=\phi(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}(\phi(n)+e(n))\
\end{aligned}
$