trudbot

本文只解决一个问题：求.

递归公式（杨辉三角)

原理

众所周知， .

定义

如果整数a, x满足, 则将x称为的模逆元， 记作.

模逆元也叫模倒数， 可以理解为模p同余式中a的倒数即, 也就是说， 模p的条件下， 是等价的。相似的有一些简单的性质如.

注意， a在模p条件下存在逆元的充分必要条件是， a与p互素。

欧几里得算法

在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

过程

欧几里得算法基于一个非常简单的原理：对于两个数a和b(a > b)， a和b的最大公约数与b和a - b的最大公约数相同。

背景

在知乎上冲浪时了解到一种很有趣的数：其所有非空后缀均为素数的数。 例如9613, 其后缀[9613, 613, 13, 3]均为素数. 而此类数的最大值为357686312646216567629137.

证明方法非常直接:用计算机枚举. 不妨为此类数随意的取个名叫做后缀素数, 不难发现, 后缀素数P的后缀必然是后缀素数. 因此对于长度为N的后缀素数必然可以由 最高位 和 一个长度为N-1的后缀素数拼接而成, 如9613可以由是9和613拼接.

欧拉通路(路径): 一条经过了图中所有边的路径， 且每条边仅经过一次。 欧拉回路: 起点和终点相同的欧拉通路。 欧拉图: 存在欧拉回路的图 半欧拉图: 不存在欧拉回路， 但存在欧拉通路的图

之所以以欧拉的名字命名， 是因为欧拉解决了与此紧密相关的一笔画问题， 即在不重复、折返的情况下遍历一张无向图。