模法导论(下)

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

随机三角形:代数篇

Aster 理宅异闻录 Leave a Comment

Q:在1-n的数里任取三个整数,其中两数之和大于第三个数的概率是多少?

A:100%

 

证明,取最大的那个数,和随便哪个数相加,合起来肯定比第三个数大....

233,好吧我知道第一眼容易把这题和三角形联系起来.

所以我们来完整的表述下:

Q:$1\sim n$的数里任取三个不重复的整数能构成三角形的概率为多少?Read More

广义勾股数组

Aster 理宅异闻录 Leave a Comment

欧拉方程是形如$\mathop \sum \limits_{i = 1}^n a_i^k = {b^k}$的方程,其中所有数字都是非零整数.

与之相关的欧拉幂和猜想是费马最终猜想的推广...啊,现在叫费马大定理了,Fermat先生实际上只证明了k=4的情形,但是最终居然不叫费马-怀尔斯定理不知道怎么搞的...记住这句话:

Cuius rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.

以后有个什么题目证不出就把这句话写上去,然后说不定以后就有个以你的名字命名的定理了...

Read More

漫无目的的旅行

Aster 理宅异闻录 Leave a Comment

随机游走可以简单的分为连续和离散两种, 前者是自然界中常见的布朗运动, 后者可以由很多数学问题化归得到.

其中, 离散情况还分为有限和无限两种类别.这里先讲第一种, 离散且有限.


例题1:有个国家有n个机场,这n个机场之间都有航班相连.我从A机场开始乘飞机,随机等概率的乘坐各架次航班在各个机场间来回.我不知道我买了哪些票,我只记得我乘了k次飞机,那么我从该架次飞机上下来后发现我在A机场的概率是多少?

Read More

语言黑洞

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

我今天又写了个德语,然后准备弃坑了,做到这份上感觉没啥意思了...

第一我发现Mathematica 10 开始的翻译功能就能翻译日文和罗马音了...亏我昨天写了半天的映射转换.

还有一个让我奔溃的就是MMA有API的来着,我咋没想到呢???Wolfram Alpha,Microsoft,Google都能用啊...

我干嘛要自己造轮子啊我勒个去...又浪费了一个礼拜的大好时光...弃坑弃坑...

Read More