给定两个函数：
设 $n$ 的唯一分解式为 $p_1^{e_1}p_2^{e_2}…p_m^{e_m}$
$$f(n) = \prod_{i=1}^{m} p_i^{2e_i + 1}+1$$
$$g(n) = \sum_{i=1}^{n} \frac{n}{\gcd(i,n)}$$
求 $\frac{f(n)}{g(n)} \mod 10^{12}$。
题解
首先直接除是不可做的，我们要把 $g$ 函数转化一下。
考虑枚举 $g$ 函数中的 $d = \gcd(i, n) (1 \le d \le n)$。由欧拉函数的定义和性质可知，满足 $\gcd(i, n) = d$ 的 $i$ 只有 $\varphi(d)$ 个。所以 $g(n) = \sum_{d|n} \frac{n}{d} \times \varphi(\frac{n}{d})$，进一步思考，我们可以得出：$g(n) = \sum_{d|n} {d} \times \varphi({d})$
定理1 $g(n)$ 是积性函数。
证明：设两个函数 $g_1(n) = n$ 和 $g_2(n) = \varphi(n)$。由于 $g_1$ 与 $g_2$ 均为积性函数。则 $g = \sum_{d|n} g_1 g_2$ 自然也是积性函数。
设 $n$ 的唯一分解式为 $p_1^{e_1}p_2^{e_2}…p_m^{e_m}$。则 $g(n) = g(p_1^{e_1}) \times g(p_2^{e^2}) \times \cdots \times g(p_m^{e_m})$。
由 phi 函数的性质可知：$\varphi(p^{e}) = (p - 1) \times p^{e-1}$，进一步得到：$\varphi(p^e) = p^e - p^{e-1}$
所以，$g(p^{e}) = \sum_{d|p^e} d \times \varphi(d) = \sum_{i = 0}^{e} p^i \times \varphi(p^i) $。
当 $i = 0$ 时，$g(p^i)$ 明显等于 $1$。
所以原式又可以化为 $= 1 + \sum_{i=1}^{e} p^i \times (p^i - p^{i - 1}) = 1 + \sum_{i = 1}^{e} p^{2i} - p^{2i-1}$。
化简，得 $g(p^{e}) = 1 - p + p^2 - p^3 + p^4 - p^5+ p^6 - \cdots - p^{2e-1} + p^{2e}$。
对其进行分组，得：$g(p^e) = 1 + (p-1) (p + p^3 + p^5 + p^7 + p^9 + \cdots + p^{2e-1})$
两式同乘 $p + 1$，得：$(p+1)g(p^e) = p + 1 + (p^2 - 1)(p + p^3 + p^5 + \cdots + p^{2e-1})$
所以：$(p + 1)g(p^e) = p + 1 + p^3 - p + p^5 - p^3 + p^7 - p^5 + \cdots + p^{2e+1} - p^{2e-1} = p^{2e+1} + 1$。
即 $g(p^e) = \frac{p^{2e+1}+1}{p + 1}$。
回到原式， $g(n) = g(p_1^{e_1}) \times g(p_2^{e^2}) \times \cdots \times g(p_m^{e_m}) = \prod_{i=1}^{m} \frac{p_i^{2e_i+1}+1}{p_i+1}$
所以，$\frac{f(n)}{g(n)} = \prod_{i-1}^{m} p_i + 1$。
所以只需把 $n$ 分解质因数即可。
使用 Pollard-rho 算法，预计时间复杂度 $O(T \times n^{\frac{1}{4}})$。
代码
1 |
|