Trick 5: 关于 GCD 的一些处理方法和性质

1. 经典的 mobius：\(\varepsilon(x) = \sum \limits_{d | x} \mu(d)\)
2. 经典的 euler：\(x = \sum \limits_{d | x} \varphi(d)\)
3. 处理区间问题。如果考虑一段区间的 \(\gcd\) ，那么固定左端点，随着右端点移动，\(\gcd\) 只会有 \(\log C\) 种取值。

CF475D

上述的模板，简单 DS。