模法导论(番外)

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慢好玄学啊.

Read More

模法导论(下)

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

高阶模法

  • 幂塔求模

下面是本模导书的重点所在了.所谓幂塔就是形如${a^{{b^c}}}$的存在,基本上c稍微大一点就是算不出来的了.大丈夫,我们不是有上面的欧拉幂模定理大法吗?

例:求4^5^6的最后两位.

$$\begin{aligned}
&\quad \ {4^{{5^6}}}\bmod 100\\
&= {4^{{5^6}\bmod \varphi (100)}}\bmod 100\\
&= {4^{15625\bmod 40}}\bmod 100\\
&= {4^{25}}\bmod 100 \\
&= 4{({4^{12}}\bmod 100)^2}\bmod 100\\
&= 4{\left( {{{\left( {4096\bmod 100} \right)}^2}\bmod 100} \right)^2}\bmod 100\\
&= \cdots = 24\quad\textbf{Wrong process!}
\end{aligned}$$

Read More

模法导论(上)

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

今年双十一我们来研究些模法.

所谓模法就是对一个数求模.

$$\begin{aligned}
a &= nq + r\quad q \in \mathbb{Z},\left| r \right| < \left| n \right| \\
r &= a\bmod q\;or\;\bmod (a,q)
\end{aligned}$$

在两数都是正数的情况下就是一个数除以另一个数的余数.也就是说正数的时候等价于求余,负数的时候就和求余相反了.

用初等函数写出来就是:

$$r = a - n\left\lfloor {\frac{a}{n}} \right\rfloor  = \frac{n}{2} - \frac{n}{\pi }\sum\limits_{k = 1}^\infty  {\frac{{\sin (2\pi k\frac{a}{n})}}{k}} $$

本模导书收录了以下模法:

  • 模法理论:归零原理,恒等原理,交换原理,分配原理
  • 初阶模法:加法求模,乘法求模,除法求模
  • 中阶模法:快速幂求模,矩阵幂求模,幂同余,欧拉幂模
  • 高阶模法:幂塔求模以及迭代幂次模
  • 无等阶模法:阶乘模和二项模

Read More

数列求通项整理

Importer 理宅异闻录 Leave a Comment

微积分里有极限、微分、积分、反常积分、微分方程、积分变换等内容

组合学里对应的有差分、求和、无穷级数、差分方程、生成函数.....

高中数列的内容可以说全是差和分方程的一部分,下面是我收集的一些数列的通项解法.此外这里把生成函数也看成数列,也就是给生成函数就不给通项了.如无特殊说明,字母均表示正整数.

Read More