欧拉繁衍
wxr_
·
·
算法·理论
\begin{aligned}
n & = \sum_{i = 1}^n \sum_{d | n} [\gcd(i, n) = d] \\
& = \sum_{d | n} \sum_{i = 1}^n [\gcd(i, n) = d] \\
& = \sum_{d | n} \sum_{i = 1}^{\frac{n}{d}} [\gcd(i \times d, n) = d] \\
& = \sum_{d | n} \sum_{i = 1}^{\frac{n}{d}} [\gcd(i, \dfrac{n}{d}) = 1] \\
& = \sum_{d | n} \varphi(\dfrac{n}{d}) \\
& = \sum_{d | n} \varphi(d)
\end{aligned}
\begin{aligned}
& \gcd(a, b, c) \\
= & \sum_{d | \gcd(a, b, c)} \varphi(d) \\
= & \sum_{d} [d | a] [d | b] [d | c] \varphi(d)
\end{aligned}
\begin{aligned}
& \sum_{i = 1}^n \gcd(i, n) \\
= & \sum_{i = 1}^n \sum_{d | \gcd(i, n)} \varphi(d) \\
= & \sum_{i = 1}^n \sum_{d} [d|i] \times [d|n] \times \varphi(d) \\
= & \sum_{d} \sum_{i=1}^n [d|i] \times [d|n] \times \varphi(d) \\
= & \sum_{d} [d|n] \times \varphi(d) \times \sum_{i=1}^n [d|i] \\
= & \sum_{d | n} \varphi(d) \times \dfrac{n}{d}
\end{aligned}
\begin{aligned}
& \sum_{i = 1}^n \sum_{j = 1}^n \gcd(i, j) \\
= & \sum_{i = 1}^n \sum_{j = 1}^n \sum_{d | \gcd(i, j)} \varphi (d) \\
= & \sum_{i = 1}^n \sum_{j = 1}^n \sum_{d} [d | i] [d | j] \varphi (d) \\
= & \sum_{d} \varphi (d) \times \lfloor \dfrac{n}{d} \rfloor ^ 2
\end{aligned}
「CF1900D」Small GCD
\begin{aligned}
& \sum_{i = 1}^n (n - i) \times \sum_{j=1}^{i-1} \gcd(a_j,a_i) \\
= & \sum_{i=1}^n (n - i) \times \sum_{j=1}^{i-1} \sum_{d|\gcd(a_j,a_i)} \varphi(d) \\
= & \sum_{i=1}^n (n - i) \times \sum_{j=1}^{i-1} \sum_{d} [d|a_i] \times [d|a_j] \times \varphi(d) \\
= & \sum_{i=1}^n (n - i) \times \sum_{d} [d|a_i] \times \varphi(d) \sum_{j=1}^{i-1} \times [d|a_j] \\
= & \sum_{i=1}^n (n - i) \times \sum_{d | a_i} \varphi(d) \times \sum_{j=1}^{i-1} [d|a_j]
\end{aligned}