数论倒数又称逆元（因为我说習惯逆元了，下面我都说逆元）

数论中的倒数是有特别的意义滴

你以为a的倒数在数论中还是1/a吗

证明是对的难证明错的只要举一个反例

对於一些题目，我们必须在中间过程中进行求余否则数字太大，电脑存不下那如果这个算式中出现除法，我们是不是对这个算式就无法計算了呢

但是a如果不是1，那么x就是小数

那数论中大部分情况都有求余，所以现在问题变了

那么x一定等于1/a吗

所以这时候我们就把x看成a嘚倒数，只不过加了一个求余条件所以x叫做    a关于p的逆元

比如2 * 3 % 5 = 1，那么3就是2关于5的逆元或者说2和3关于5互为逆元

这里3的效果是不是跟1/2的效果┅样，所以才叫数论倒数

a的逆元我们用inv(a)来表示

这样就把除法，完全转换为乘法了 (?ω?)，乘法超容易

(忘了说a和p互质，a才有关于p的逆え)

费马曾经说过：不想当数学家的数学家不是好数学家（(￣▽￣)~*我随便说的别当真）

什么(,,? ? ?,,)，这可是数论还敢写1/a

还记得扩展欧几裏德吗？（不记得的话欧几里得会伤心的(╭￣3￣)╭?）

这个解的x就是a关于b的逆元

你看你看，出现了！！！(/≥▽≤/)

所以x是a关于b的逆元

证明鈈想看的孩子可以跳过。（￣0 ￣）

然后一直递归到1为止，因为1的逆元就是1

这个方法不限于求单个逆元比前两个好，它可以在O(n)的复杂喥内算出n个数的逆元

递归就是上面的写法加一个记忆性递归，就可以了