只要求一个时，使用拓展欧几里得算法即可，代码如下：

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为质数，根据需要，可以不循环那么多次