花火

在某TS的推荐下去这儿申请了个blog。最诱人的地方在于它天然支持语法加亮和tex公式。不过简单试用后发现，它的tex和语法加亮全部是要经过数次鼠标点击才能完成的，这对追求速度常用键盘的programmers来说是个很大的弊端。
于是在那边贴了我的某文里头的一部分，也贴在这儿对比一下效果吧。
PS:好吧，这儿的效果也囧，果然这个JS和真正的tex还是有很大差距的…在这边也一样要进行很多修改

同余是一门古老的学问。中国古代对同余问题进行了深入的研究，并且获得了许多漂亮的结论。下面先对同余知识进行介绍。

同余问题所研究的是余数，假设整数n可以被表示为`n=px+r, p,x,r \in Z`，那么r就是n除p的余数，也叫n模p的值。如果a和b除p的余数相同，那么写成式子是这样：`a \equiv b \pmod{p}`。注意，广义情况下这个b不一定是非负数，负数的情况下意义与各种计算机语言中`mod`或者\% 的意义不同。具体意义下面再说。

同余式的两边可以加减任何整数。而r为负数的情况也是由此产生的。如`100 \equiv 1 \pmod{3} \Rightarrow 97 \equiv -2 \pmod{3}`。同余式两边可以同时乘一个数。比如`100 \equiv 1 \pmod{3} \Rightarrow 200 \equiv 2 \pmod{3}`。同余式两边也可以同时除以一个数，如果除得的结果都是整数且这个除数与模互质。当然，再继续推广下去，同余式两边也不一定是整数，只要有理就行。不过一般我们不这么推广，还是认为同余式中的所有数都应该是整数。类似的，我们可以将两个模相同的同余式相加、减、乘。

下面介绍Fermat小定理。
`a^{p-1} \equiv 1 \pmod{p}`
其中p为素数，`a<p, a\inZ*`。这个定理的证明很巧妙，我认为也有必要介绍一下。

首先我们需要这样一个结论，如果p是一个素数，那么对任何`a<p, a\inZ*`，`a, 2a, 3a, \ldots, (p-1)a`，这些数对p的模恰好是1到(p-1)的某个排列。
反证，首先这些数之中显然不会有任何一个模p为0，那么假设命题不成立，由抽屉原理，必有某个`ia`和`ja`对p的模相等。不妨假设`i>j`，那么`(i-j)a`一定可以整除p，这与前面的结论矛盾，因此命题成立。
接下来，将这些数字全部乘起来，求他们的积对p的模。根据前面的结论，可以得到这样一个同余式
`(p-1)!a^{p-1} \equiv (p-1)! \pmod{p}`
显然`(p-1)!`与`p`互素，于是两边除`(p-1)!`即可得证。

GCD是欧几里德法求最大公约数的简称。这个方法是如此著名而简单。假设我们希望求`a`和`b`的最大公约数，定义函数
`(a,b)=gcd(a,b)=\begin{cases} gcd(b, a\%b), & b\ne0 \ a, & b=0 \end{cases}`
这就是gcd。实现时可以直接递归实现，或者可以非递归用个while实现。不过gcd有一些很不寻常的写法，比如不用模运算的方法，那些属于歪门邪道，还是不作介绍。它的复杂度粗略是`O(logn)`。
下面我们来介绍拓展欧几里德法。如果`(a,b)=d`，那么必定存在整数`x,y`满足方程`ax+by=d`。我们可以通过拓展欧几里德法来求出一个可行的`x,y`。具体方法也是迭代，相比数学表示还是程序表达比较方便。

    int exgcd(int a, int b, int &x, int &y)
    {
      if (b==0) {x=1; y=0; return a;}
      exgcd = exgcd(b, a\%b, x, y);
      int t=x; x=y; y=t-((int)(a/b))*y;
    }

为了理解这个程序，我们可以倒过来看。递归到最后一层的时候`b=0`，那么方程`ax+by=d`此时的解显然是`x=1, y=0`。而当递归到某中间层的时候，如果我们能求出`bx'+(a-\left \lfloor \frac{a}{b} \right \rfloor)y' = d`的解`x', y'`，通过对方程简单的变形就可以发现，
`bx'+(a-\left \lfloor \frac{a}{b} \right \rfloor)y' = d \Leftrightarrow y'a + (x' - \left \lfloor \frac{a}{b} \right \rfloor y')b = d`
于是原方程`ax+by=d`的解就是`x=y', y= (x' - \left \lfloor \frac{a}{b} \right \rfloor y')`。