模法导论(番外)

Aster CODE➤GEASS, 理宅异闻录 Leave a Comment

说说两个有趣的关于求模的算法.

第一个是阶乘求模.这个么,其实规模小的时候$\left( {a!\bmod n\quad a < n < {{10}^6}} \right)$也没什么优化可用.硬刚吧.

  1. 先朴素的把这个数算出来然后求模0.23s,good.
  2. 自己造个轮子把数算出来然后求模,0.70s,233,说了不要自己造轮子.
  3. 用Fold折叠列表,边乘边模,0.12s,Excellent! 如果是Haskell的话应该会更快吧,第一有惰性计算,第二乘法计算速度真的丧心病狂,当初刷OJ直接写a*b过了大数乘法,而且还是第一.......
  4. 所以我们想能不能从两边一起折叠这个列表,Sorry,MMA没有这种的,然后想到要是对折这个列表岂不是可以有${\log _2}n$的算法了?想得美,0.82s.
  5. 好吧对折太慢了,应该一次折叠100重,0.23s.Well,看来多出来的那么多次乘法和取模不管怎样反而消耗了更多的资源呐.
  6. 所以我们来用循环吧!1.02s,666,说了MMA里能不用循环就不要用循环,特别是不编译直接正面刚,而且用了编译还不如全部用C#写然后Link进来.我用C#写了个naïve的循环确实是0.1s左右.
  7. 想到个折中的办法,Nest尾递归一个二元组就不用维护列表了.0.16s,唔,不是很懂怎么搞的,会比Fold慢好玄学啊.


为什么不用和快速幂模类似的算法呢?实在是a小的时候没啥用还不如Fold硬刚,a大的时候又有更好的选择了.

$a!\bmod n\quad a >  > n > {10^6}$时

威尔逊定理说:

$$(p - 1)!\; \equiv \; - 1\bmod p$$

证:如果$p$是个质数,那么$1,2,3,...,p - 2,p - 1$都和$p$互质

$$\begin{aligned}
(p - 2)! &\equiv {((p - 2)!)^{p - 1}} \equiv 1\bmod p \\
\Rightarrow (p - 1)! &\equiv (p - 1) \cdot 1 \equiv - 1\bmod p\quad\square
\end{aligned}$$

正着用这个定理一点用都没有,本来判定大质数就够烦了,居然还要来求阶乘,你是在搞笑吗?!朴素(naïve)的试除法的复杂度才$O(\sqrt n )$.

嘛,其实这个暗示了反过来也是有大约这个速度的算法的.我们想个办法把阶乘分解成数阵,令$m = \sqrt {a - 1} \;$

$$P(x) = (x + 1)(x + 2) \cdots (x + m)$$

$$\begin{array}{*{20}{l}}
{P(0)}&{0 + 1}&{0 + 2}& \cdots &{0 + m}&{(1m)} \\
{P(m)}&{m + 1}&{m + 1}& \cdots &{m + m}&{(2m)} \\
{P(2m)}&{2m + 1}&{2m + 2}& \cdots &{2m + m}&{(3m)} \\
\cdots\cdots&\cdots\cdots&\cdots\cdots&\cdots&\cdots\cdots\cdots&\cdots\cdots&\\
{P(m(m - 1))}&{m(m - 1) + 1}&{m(m - 1) + 2}& \cdots &{m(m - 1) + m}&{({m^2})}
\end{array}$$

 

左右乘起来

$$\begin{aligned}
a! &= aP(0)P(m) \cdots P(m(m - 1))\\
a!\,\bmod \,n &= \left( {a\,\bmod \,n\prod\limits_{i = 0 + m}^{m(m - 1)} {P(mi)\,\bmod \,n} } \right)\,\bmod \,n
\end{aligned}$$

如果开根不是整数那么就下取整然后把缺掉的部分补上就行了.

用类FFT算法,计算量瞬间砍掉一半.理论上把复杂度从$O\left( n \right)$降到了$O\left( {{n^{0.5 + \varepsilon }}} \right)$,而且其实还能优化,模质数的时候也能掉用点数论.但是在n小的时候表现并不好,所以可以用一个复合策略来再度优化,我反正懒得干了,就补一个朴素的例子吧,0.045s.

算了,写的还是不好,比这个C写的慢了10多倍.


第二个就是求组合数的模了.

模质数的时候有卢卡斯定理:

$$\begin{aligned}
m &= {m_k}{p^k} + {m_{k - 1}}{p^{k - 1}} + \cdots + {m_1}p + {m_0}\\
n &= {n_k}{p^k} + {n_{k - 1}}{p^{k - 1}} + \cdots + {n_1}p + {n_0}\\
\left( \begin{gathered}
m \\n \\
\end{gathered} \right) &\equiv \prod\limits_{i = 0}^k {\left( \begin{gathered}
{m_i} \\{n_i} \\
\end{gathered} \right)} \bmod p
\end{aligned}$$

证:

$$\begin{aligned}
\left( \begin{gathered}
p \\n \\
\end{gathered} \right) &= \frac{{p \cdot (p - 1) \cdots (p - n + 1)}}{{n \cdot (n - 1) \cdots 1}}\\
{(1 + X)^p} &\equiv 1 + {X^p}\bmod p\\
{(1 + X)^{{p^i}}} &\equiv 1 + {X^{{p^i}}}\bmod p
\end{aligned}$$

$$m = \sum\limits_{i = 0}^k {{m_i}} {p^i}$$

$$\begin{aligned}
\sum\limits_{n = 0}^m {C(m,n){X^n}} &= {(1 + X)^m} \hfill \\
&= \prod\limits_{i = 0}^k {{{\left( {{{(1 + X)}^{{p^i}}}} \right)}^{{m_i}}}}\\
&= \prod\limits_{i = 0}^k {\sum\limits_{{n_i} = 0}^{{m_i}} {C({m_i},{n_i}){X^{{n_i}{p^i}}}} }\\
&= \prod\limits_{i = 0}^k {\sum\limits_{{n_i} = 0}^{p - 1} {C({m_i},{n_i}){X^{{n_i}{p^i}}}} }\\
&= \sum\limits_{n = 0}^m {\prod\limits_{i = 0}^k {C({m_i},{n_i}){X^n}} } \;\,\bmod \,\;p\\
C(m,n) &\equiv \prod\limits_{i = 0}^k {C({m_i},{n_i})} \;\,\bmod \,\;p\quad \square
\end{aligned}$$

不过这个只能模质数,OJ的时候倒是少有不是模质数的.有点求知欲好不好,难道做题用不到就不推了吗?

卢卡斯定理揭示了杨辉三角和谢宾斯基三角之间的联系.


从这个演示上可以看出其实非模p的情况是各种模p的情况的叠加.

我们来一步步推导,先讨论纯素数叠加的形式,即假设n无平方因子,也就是说$n = {p_0} \cdot {p_1} \ldots  \cdot {p_r}$,分别求解$C[n,k]\bmod \,{p_i}$,得到解${a_0},{a_1}, \ldots ,{a_r}$.嗯,然后怎么把解合起来呢?

啊哈,中国剩余定理.

$$\left\{ \begin{gathered}
x \equiv {a_0}\bmod {p_0} \hfill \\
x \equiv {a_1}\bmod {p_1} \hfill \\
\cdots \cdots \cdots \cdots \cdots \hfill \\
x \equiv {a_r}\bmod {p_r} \hfill \\
\end{gathered} \right.$$

中国剩余定义的适用条件是所有的模都要是质数,当然满足啦.

但是这样又钦点了n无平方因子,得用更强的手段去掉这个条件.

Andrew Granville定理给出了模${p^k}$时的结论.

$$\frac{1}{{{p^{{e_0}}}}}\left( \begin{gathered}
n \\m \\
\end{gathered} \right) \equiv {( \pm 1)^{{e_q} - 1}}\left( {\frac{{{{({N_0}!)}_p}}}{{{{({M_0}!)}_p}{{({R_0}!)}_p}}}} \right)\left( {\frac{{{{({N_1}!)}_p}}}{{{{({M_1}!)}_p}{{({R_1}!)}_p}}}} \right)...\left( {\frac{{{{({N_d}!)}_p}}}{{{{({M_d}!)}_p}{{({R_d}!)}_p}}}} \right)\quad \bmod \,{p^q}$$

这个定理看上去复杂实现起来也很复杂,我就不在这里写了.已同步到BiGridGenerator程序包.

这里只给出前两种情况


推荐阅读:
http://math.stackexchange.com/questions/60206/lucas-theorem-but-without-prime-numbers
http://fishi.devtail.io/weblog/2015/06/25/computing-large-binomial-coefficients-modulo-prime-non-prime/
http://fredrikj.net/blog/2012/03/factorials-mod-n-and-wilsons-theorem/

发表评论