程序设计竞赛模板之乘法逆元

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注