逆元：（即是逆元素）逆元素是指一個可以取消另一給定元素運算的元素。

在一個代數系統（S，*）中，存在單位元素e，如果對S內的元素a存在a^-1 * a = e，則將 a^-1稱為a 的左逆元。

同理若存在 a * a^-1 = e，則將a^-1 稱為a 的右逆元。

這里的左逆元和右逆元是針對給定運算的某個元素而言的。我們說某個元素有沒有逆元素，而不能說某個代數系統有沒有逆元素。 另外還需要說明： (1)一個元素可以沒有左逆元和右逆元； (2)一個元素可以只有左逆元； (3)一個元素可以只有右逆元； (4)一個元素可以既有左逆元，又有右逆元。
左右逆元素相等且唯一的條件是：
1)運算有單位元素； 2)元素a的左右逆元素都存在； 3)滿足結合律。 通過以上分析，我們得出如下定理： 定理1　　?設 ? 為S上可結合的二元運算，e為該運算的單位元，對于x∈S，如果存在左逆元?和右逆元??，則有且y是x的唯一的逆元。 ? 在求解 (a+b)%c, (a-b)%c, (a*b)%c 的時候，無論a,b,c多大，都可以轉換成 a%c + b%c, a%c-b%c, a%c*b%c，然后直接進行運算。 但是在算 (a / b)%c 的時候，并不能直接轉化成 a%c / (b%c)。 比如 5 / 2 % 3，在進行正常的運算時： 5/2 = 2 , 2%3 = 2，所以結果應該是 2 如果轉化成 （5%3）/（2%3）= 2 / 2 = 1，所以結果變成了1。 費馬小定理： 假如p 時一個質數，且gcd(p ,1) = 1，那么 a^(p-1)?≡ 1 (mod p) a / b % c ≡ a * b^-1 % c?≡ a %c * b^-1 % c，其中 b^-1 為b 的逆元，當c是個素數，且b不是c的倍數的時候： b ^(c - 1)?≡ 1 (mod c)，b * b^(c-2)?≡ 1 (mod c)，于是b 的逆元就是 b^(c-2) 。 當c比較大的時候，需要用快速冪。 擴展歐幾里得： 給定模數m，求a的逆相當于求解a*x=1(mod m)
這個方程可以轉化為a*x-m*y=1?
然后套用求二元一次方程的方法，用擴展歐幾里得算法求得一組x0,y0和gcd?
檢查gcd是否為1?
gcd不為1則說明逆元不存在?
若為1，則調整x0到0~m-1的范圍中即可 1 LL inv(LL t, LL p) 2 { 3 if(t == 1) 4 return 1; 5 return (p - p / t) * inv(p % t, p) % p; 6 }

這是求t關于p 的逆元。

轉載于:https://www.cnblogs.com/ouyang_wsgwz/p/8688255.html

總結

以上是生活随笔為你收集整理的逆元+费马小定理+扩展欧几里得的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。