21xrx.com
2024-12-22 22:08:43 Sunday
登录
文章检索 我的文章 写文章
求解c++中mod的逆运算
2023-06-28 12:54:28 深夜i     --     --
C++ mod 逆运算 算法 数学

在c++中,模运算(mod)是一种常见的数学运算,用于取余数。例如,7 mod 3的结果为1,因为7除以3等于2余1。但是,有时候我们需要求解mod的逆运算,也就是找到一个数x,使得a mod b = x,其中a和b已知,而x则是未知的。

为了求解mod的逆运算,我们需要使用扩展欧几里得算法(extended Euclidean algorithm)。该算法是基于欧几里得算法(Euclidean algorithm)的扩展版本,用于求解两个数的最大公约数,同时还能够找到两个数的一组贝祖等式(Bézout's identity)。

扩展欧几里得算法的基本原理如下:

假设我们需要求解p和q的最大公约数(gcd)。我们从p和q的余数r0开始,将r0赋值给变量r1,将q除以r0的商赋值给变量q1。重复该过程直到余数为0,此时q1就是gcd。

那么如何找到贝祖等式呢?我们需要维护两个变量s和t,每次更新它们的值。其中s和t的初始值分别为1和0。在每一步中,我们计算 r0 = p % q, 并将p除以q的商赋值给变量p1。然后,我们更新s和t的值为 s = t, t = s - q1 * t,最终得到 s 和 t,它们满足以下等式:

s * p + t * q = gcd(p, q)

现在我们可以使用扩展欧几里得算法来求解mod的逆运算。假设我们需要找到x,使得a mod b = x。我们可以使用以下公式:

a * s + b * t = gcd(a, b)

因为gcd(a, b) = 1,所以可以简化为:

a * s + b * t = 1

现在我们只需要把等式两边同时模b,得到:

a * s mod b = 1

因此,s就是mod的逆运算,即x的值。代码实现如下:


int modInverse(int a, int b) {

  int s = 0, t = 1, r = b, r1, s1, q;

  while (a != 0) {

    q = r / a;

    r1 = r % a;

    s1 = s - q * t;

    s = t;

    t = s1;

    r = a;

    a = r1;

  }

  if (r > 1)

    // a和b不互质

    return -1;

  

  if (s < 0) {

    s += b;

  }

  return s;

}

这个函数接受两个参数a和b,分别代表被模数和模数。它返回mod的逆运算,或者如果a和b不互质则返回-1。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复