只要求一个时,使用拓展欧几里得算法即可,代码如下:
int extgcd(int a, int b, int& x, int& y) { int d = a; if (b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1;y = 0; } return d; }
如果求一连串的,可以使用递推公式,代码如下:
int inv[MAXN]; inv[1] = 1; for(int i = 2; i < p; ++ i) inv[i] = (p - p / i) * inv[p % i] % p; //p为质数,根据需要,可以不循环那么多次