近期做的两道题。

Problem

ProjetEuler-429

定义 $d$ 是 $n$ 的单位因子，当且仅当 $gcd(d, \frac{n}{d}) = 1$ 。

令 $f(n)$ 表示 $n$ 的所有单位因子的平方和。例如 $f(24) = 1^2 + 3^2 + 8^2 + 24^2 = 650$

求 $f(10^8 !)$

湖大 ACM 区域赛 A

求 $\lceil (a + \sqrt{b})^n \rceil \mod{m}$ 。

$b, n \leq 2^{30}, a, m \leq 2^{15}$

保证 $(a - 1)^2 < b < a^2$ 。

Solution

ProjetEuler-429

显然 $f$ 积性。

显然 $f(p^x) = 1 + p^{2x}$ 。

然后线性筛法筛过去没了。

湖大 ACM 区域赛 A

注意到：

$$(a + \sqrt{b})^n + (a - \sqrt{b})^n = \sum_{x = 0}^n \binom{n}{x} a^{n - x} \left(\sqrt{b^x} + (-\sqrt{b})^x \right).$$

当 $x$ 为奇数时 $(\sqrt{b})^x + (-\sqrt{b})^x = 0$ ，当 $x$ 为偶数时 $(\sqrt{b})^x + (-\sqrt{b})^x$ 为整数，所以 $(a + \sqrt{b})^n + (a - \sqrt{b})^n$ 为整数，又由于 $0 < a - \sqrt{b} < 1$ 所以 $\lceil (a + \sqrt{b})^n \rceil = (a + \sqrt{b})^n + (a - \sqrt{b})^n$ 。

现在考虑求 $(a + \sqrt{b})^n + (a - \sqrt{b})^n$ 。我们可以把它看成是一个二阶线性齐次递推式的通项公式，只要还原出递推式出来，就可以用矩阵乘法了。

考虑 $x_1 = 2a, x_2 = 2a^2 + 2b, x_n = p x_{n -1} + q x_{n - 2}$ 。特征根方程是 $x_2 - px - q = 0$ 。我们知道两个根分别是 $a + \sqrt{b}$ 和 $a - \sqrt{b}$ ，韦达可得 $p = 2a, q = b - a^2$ ，所以 $x_n = 2a x_{n - 1} + (b - a^2) x_{n - 2}$。

如果考虑直接求 $\bmod{m}$ 的循环节长度然后暴力不知道怎么样。