在《孙子算经》中有这样一个问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何?

这个问题说的是，有一件物品，我们不知道它的数量。但是，如果三个三个数，最后会剩下两个；如果五个五个数，最后会剩下三个；如果七个七个数，最后会剩下两个。问这个东西的数量是多少？

实际上，这个问题在现在我们可以将其转化为一个同余方程组：

$$\left\{ \begin{aligned} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \\ x \equiv 2 \pmod 7 \end{aligned} \right.$$

中国剩余定理告诉了我们像这样的同余方程组的解。这个定理又称为孙子定理，通常被简写成CRT（Chinese Remainder Theorem）。

这篇文章将会从欧几里得算法开始讲起，之后过渡到扩展欧几里得算法解线性方程，最后介绍中国生于定理。

(more…)

Read More

首先我们从求前 $n$ 个整数的平方和开始，也就是

$$S_n = \sum_{i=1}^n n^2$$

然后可以尝试对 $S_n$ 进行“扰动”，就像这样

$$\begin{eqnarray*} S_n + (n + 1)^2 &=& \sum_{i=0}^n (i+1)^2 \\ &=& \sum_{i=0}^n (i^2 + 2i + 1) \\ &=& S_n + 2\sum_{i=1}^n i + (n + 1) \\ \end{eqnarray*}$$

最后发现 $S_n$ 竟然被消掉了，“扰动”失败了，但是我们注意到这求出了 $\sum_{i=1}^n i$ 的公式

所以会想，可不可以用更高的 $C_n = \sum_{i=1}^n i^3$ 来求出 $S_n$

$$\begin{eqnarray*} C_n + (n + 1)^3 &=& \sum_{i=0}^n (i+1)^3 \\ &=& \sum_{i=0}^n (i^3 + 3i^2 + 3i + 1) \\ &=& C_n + 3S_n + \frac{3n(n + 1)}{2} + (n + 1) \\ \Rightarrow S_n &=& \frac{(n+1)^3 - \frac{3n(n + 1)}{2} - (n + 1)}{3} \\ &=& \frac{n(n+\frac{1}{2})(n+1)}{3} \end{eqnarray*}$$

于是这样成功地求出了 $S_n$ 的公式，既然如此，我们又会去尝试计算更高阶的幂和

(more…)

Read More

前几天在看 lucas 定理的时候发现要求 $1,~2,\cdots,p-1\bmod p$ 的逆元，然后就看到了一个 $\Theta(n)$ 的做法发现太神了，虽然想起来是挺简单的

这个做法实际上是这样的，首先 $1^{-1} \equiv 1 \pmod p$

然后我们设 $p = k\cdot i + r,~r < i,~1 < i < p$

再将这个式子放到$\mod p$ 意义下就会得到

$$k\cdot i + r \equiv 0 \pmod p$$

两边同时乘上 $i^{-1}\cdot r^{-1}$ 就会得到

$$\begin{eqnarray*} k\cdot r^{-1} + i^{-1} &\equiv& 0 &\pmod p\\ i^{-1} &\equiv& -k\cdot r^{-1} &\pmod p\\ i^{-1} &\equiv& -\left\lfloor\frac{p}{i}\right\rfloor\cdot \left(p\bmod i\right)^{-1} &\pmod p\ \end{eqnarray*}$$

于是就可以从前面推出当前的逆元了，代码也就一行

Read More