PE-429-and-HNU-A

近期做的两道题。

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}\) 的循环节长度然后暴力不知道怎么样。