题目出自東京工業大学プログラミングコンテスト2019（TTPC2019）

题目链接 https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_i

题意

对于正整数 \(x\) 定义函数 \[ f(x) := \begin{cases} f(\frac{x}{P}) \quad & \text{if $x \equiv 0 \pmod{P}$} \\ x & \text{otherwise} \end{cases} \]

给你整数 \(P, Q, L, R\)，输出下列式子的值 \[ \left(\prod_{i=L}^{R} f(i) \right) \bmod Q \]

限制

• \(2 \le P, Q \le 10^7\)
• \(1 \le L \le R \le 10^{18}\)

解法

这是一个笨方法。

我们要计算 \(\prod_{i=L}^{R} f(i) \bmod Q\)。利用中国剩余定理，只要我们能算出 \[ \prod_{i=L}^{R} f(i) \bmod q^{\alpha} \] 即可。这里 \(q\) 是素数，是 \(Q\) 的一个素因子。

计算 \(\prod_{i=L}^{R} f(i) \bmod q^{\alpha}\)

\(\prod_{i=L}^{R} f(i)\) 可表为 \[ \frac{\prod_{i=1}^{R} f(i)}{\prod_{i=1}^{L-1} f(i)}. \] 为了计算 \(\frac{\prod_{i=1}^{R} f(i)}{\prod_{i=1}^{L-1} f(i)} \bmod q^{\alpha}\)，对于乘积 \(\prod_{i=1}^{n} f(i)\)，我们把其中的因子 \(q\) 分解出来，写成 \[ \prod_{i=1}^{n} f(i) = q^{\nu_q(\prod_{i=1}^{n}f(i))} \cdot (\prod_{i=1}^{n}f(i))_q. \] 问题就归结为计算 \[ \nu_q(\prod_{i=1}^{n}f(i)) \] 和 \[ (\prod_{i=1}^{n}f(i))_q \bmod q^{\alpha}. \]

计算 \(\nu_q(\prod_{i=1}^{n}f(i))\) 和 \((\prod_{i=1}^{n}f(i))_q \bmod q^{\alpha}\)

注意到 \[ \prod_{i=1}^{n} f(i) = {n!\over P^{\lfloor n/P \rfloor + \lfloor n/P^2 \rfloor + \lfloor n/P^3 \rfloor + \dots}} \]

解释：\(1, 2, \dots, n\) 中，能被 \(P\) 除至少 \(1\) 次的数有 \(\lfloor n/ P \rfloor\) 个，能被 \(P\) 除至少 \(2\) 次的数有 \(\lfloor n/P^2 \rfloor\) 个，……

令 \(\nu(n!,P) = \lfloor n/P \rfloor + \lfloor n/P^2 \rfloor + \lfloor n/P^3 \rfloor + \dots\)，于是 \[ \prod_{i=1}^{n} f(i) = \frac{n!}{P^{\nu(n!,P)}}. \] 为了计算 \(\nu_q(\prod_{i=1}^{n}f(i))\) 和 \((\prod_{i=1}^{n}f(i))_q \bmod q^{\alpha}\)，先把分子和分母对素数 \(q\) 做一个分解。 \[ n! = q^{\nu_q(n!)} \cdot (n!)_q \\ P^{\nu(n!,P)} = q^{\nu_q(P)\cdot \nu(n!,P)} \cdot (P)_q^{\nu(n!,P)} \] 于是 \[ \nu_q(\prod_{i=1}^{n}f(i)) = \nu_q(n!) - \nu_q(P)\cdot \nu(n!,P) \\ (\prod_{i=1}^{n}f(i))_q = \frac{(n!)_q}{(P)_q^{\nu(n!,P)}} \] 计算 \((\prod_{i=1}^{n} f(i))_q \bmod q^{\alpha}\) 就归结为计算 \((n!)_q \bmod q^{\alpha}\)。

计算 \((n!)_q \bmod q^{\alpha}\)

我们把 \(1, 2, \dots, n\) 做一个分类：

• 与 \(q^{\alpha}\) 互素的
• 与 \(q^{\alpha}\) 不互素的

也就是与 \(q\) 互素的，和与 \(q\) 不互素的。或者说 \(q\) 的非倍数和 \(q\) 的倍数。

\(1, 2,\dots, n\) 中和 \(q^{\alpha}\) 互素的数的乘积除以 \(q^{\alpha}\) 的余数，根据 Wilson 定理的推广，可表为 \[ ((\pm 1)^{\lfloor n/q^{\alpha} \rfloor}\cdot \prod_{1 \le i \le (n\bmod q^\alpha),q\not\mid i} i) \bmod q^\alpha \] \(1, 2, \dots, n\) 和 \(q^{\alpha}\) 不互素的数，对乘积 \((n!)_q\) 的贡献可写成 \((\lfloor n/q \rfloor!)_q\)。