逆元计算方法详解？

本文共计2735个文字，预计阅读时间需要11分钟。

今天我们来探讨逆元在ACM-ICPC竞赛中的应用，逆元是一个非常重要的概念，必须学会使用它。对于整数a和b，如果存在整数x和y，使得ax + by=1，则称a和b互质，a关于b的逆元为x。例如，对于整数5和7，它们的逆元是3，因为5*3 + 7*(-2)=1。逆元通常称为模的逆元。

今天我们来探讨逆元在ACM-ICPC竞赛中的应用，逆元是一个很重要的概念，必须学会使用它。

对于正整数

和

，如果有

，那么把这个同余方程中

的最小正整数解叫做

模

的逆元。

逆元一般用扩展欧几里得算法来求得，如果

为素数，那么还可以根据费马小定理得到逆元为

。

推导过程如下

求现在来看一个逆元最常见问题，求如下表达式的值（已知

）

当然这个经典的问题有很多方法，最常见的就是扩展欧几里得，如果

是素数，还可以用费马小定理。

但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的，它们都会要求

与

互素。