数论倒数又称逆元(因为我说習惯逆元了,下面我都说逆元)
数论中的倒数是有特别的意义滴
你以为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个数的逆元
递归就是上面的写法加一个记忆性递归,就可以了