求解c++中mod的逆运算 |21xrx.com

求解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。

上一篇: idea打包java可执行jar包

下一篇: C++结构体与C结构体的不同点

评论区

()

相似文章