数学相关

逼近数列：

---

$$\begin{array}{c} \begin{cases} \alpha_{\scriptscriptstyle {2k-1}}^{\scriptscriptstyle {(a,b)}} &= \frac{ \left( a + \sqrt{a^2+b} \right)^{2^{\scriptscriptstyle{k-1}}} + \left( a - \sqrt{a^2+b} \right)^{2^{\scriptscriptstyle{k-1}}} }{2} \\ \alpha_{\scriptscriptstyle {2k}}^{\scriptscriptstyle {(a,b)}} &= \frac{ \sqrt{a^2+b} \left[ \left( a + \sqrt{a^2 + b} \right)^{2^{\scriptscriptstyle {k-1}}} - \left( a - \sqrt{a^2 + b} \right)^{2^{\scriptscriptstyle {k-1}}} \right] }{2\left( a^2 + b \right)} \end{cases} \\ \Updownarrow \\ \begin{cases} \alpha_{\scriptscriptstyle{2k-1}}^{\scriptscriptstyle{(a,b)}} = \left[ \alpha_{\scriptscriptstyle{2k-3}}^{\scriptscriptstyle{(a,b)}} \right]^2 + (a^2+b)\left[ \alpha_{\scriptscriptstyle{2k-2}}^{\scriptscriptstyle{(a,b)}} \right]^2 \\ \alpha_{\scriptscriptstyle{2k}}^{\scriptscriptstyle{(a,b)}} = 2\alpha_{\scriptscriptstyle{2k-2}}^{\scriptscriptstyle{(a,b)}} \alpha_{\scriptscriptstyle{2k-3}}^{\scriptscriptstyle{(a,b)}} \\ \alpha_{\scriptscriptstyle{1}}^{\scriptscriptstyle{(a,b)}} = a, \alpha_{\scriptscriptstyle{2}}^{\scriptscriptstyle{(a,b)}} = 1, a,k \in \mathbb{N}_{\scriptscriptstyle+} ~ , k \ge 2 ~ , b \in \mathbb{Z} \end{cases} \end{array}$$

---

快速求和：

求 $\sum_{i = 1}^{n}[\gcd(i, n) = k]$ 的值：

$$\begin{aligned} \text{原式} &= \sum_{i = 1}^{n} [\gcd(i, n) = k] \\ &= \sum_{i = 1}^{\lfloor n/k \rfloor} \left[ \gcd\left(i, \left\lfloor \frac{n}{k} \right\rfloor\right) = 1 \right] \\ &= \sum_{i = 1}^{\lfloor n/k \rfloor} \sum_{d \mid \gcd(i, \lfloor n/k \rfloor)} \mu(d) \\ &= \sum_{i = 1}^{\lfloor n/k \rfloor} \sum_{d = 1}^{\lfloor n/k \rfloor} [d \mid i] \cdot [d \mid \lfloor n/k \rfloor] \cdot \mu(d) \\ &= \sum_{d \mid \lfloor n/k \rfloor} \mu(d) \sum_{i=1}^{\lfloor n/k \rfloor} [d \mid i] \\ &= \sum_{d \mid \lfloor n/k \rfloor} \mu(d) \cdot \frac{\lfloor n/k \rfloor}{d} \\ &= \varphi\left( \left\lfloor \frac{n}{k} \right\rfloor \right) \end{aligned}$$

得求。

---

莫比乌斯函数和欧拉函数的性质：

$$\begin{align} \sum_{d|n}{\mu(d)=[n == 1]} \\ \sum_{d|n}{\mu(d)\frac{n}{d}}=\varphi(n) \\ \sum_{d|n}{\varphi(d)}=n \\ \end{align}$$