題目大意

給定 $n$（$1\le n\le 1000$）個正整數(shù) $a_1, a_2, \dots, a_n$（$a_i \le 10^{12}$），令 $s$ 為這 $n$ 個數(shù)之和。求
$$
\frac{s! } {\prod\limits_{1\le i\le n} a_i !} \bmod 10
$$

解法

中國剩余定理。

設(shè)上式中左邊的商為 $x$，先分別求出 $x \bmod 2$ 和 $x\bmod 5$， 再利用中國剩余定理就可求得答案。

這個問題歸結(jié)為：
對于素數(shù) $p$ 和正整數(shù) $n$，將 $n!$ 寫成 $n! = ap^{k}$，且 $p$ 不是 $a$ 的因子。求 $a$ 和 $k$ 。

不難發(fā)現(xiàn)：
設(shè) $n$ 的 $p$-進制展開式為
$$ n = b_0 + b_1 p + b_2 p^2 + \dots + b_r p^r \qquad ( 0 \le b_i \in \mathbb{Z} < p, b_r > 0) $$

則有
\begin{align}
k & = [n/p] + [n/p^2] + [n/p^3] + \dots + [n/p^r] \\
a & \equiv (p-1)!^{k} b_0! b_1! \dots b_r! \pmod{p} \label{Eq:2}
\end{align}

其中 $[x]$ 表示不超過 $x$ 的最大整數(shù)。
（令 $B = b_0 + b_1 + ... + b_r$，不難證明，$k$ 還可以寫成 $k = \frac{n - B}{p-1}$）

根據(jù) Wilson 定理，\eqref{Eq:2} 可寫成
\begin{equation}
a \equiv (-1)^{k} b_0! b_1! \dots b_r ! \pmod{p}
\end{equation}

算法的復(fù)雜度為 $O(p + \log_p n)$ 。

從這個問題中積累的新模型
一、$\frac{A}{B}\bmod p$（$B$ 能整除 $A$ 且 $p$ 是素數(shù)）的解法。
二、$n! \bmod p$（$p$ 是素數(shù)） 的解法。

---

下面考慮：模數(shù)不是 $10$ 而是 $20$ 的情況下，此題如何求解。

仍循舊思路，采用中國剩余定理，我們需要求出 $x \bmod 4$；按舊辦法求當(dāng)然是可以的。注意：由于要預(yù)處理出 $0$ 到 $p-1$ 的階乘，所以（對于舊思路）能否用 Wilson 定理并不影響復(fù)雜度。

如果模數(shù)的某個素因子的次數(shù) $k$ 很高，求 $x \bmod p^k$ 的復(fù)雜度 $O(p^k + \log_{p^k} n)$ 就不能容忍了。很自然地，我們會考慮 $x\bmod p$ 與 $x\bmod p^k$ 之間的關(guān)系。
（留坑）

轉(zhuǎn)載于:https://www.cnblogs.com/Patt/p/8166565.html

總結(jié)

以上是生活随笔為你收集整理的hihoCoder #1639 图书馆的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。