模数求逆内置函数，C++

Question

在编程中，有一种非常好的方法可以找到模反元素（也就是给定 a 和 m，满足 ab ≡ 1 (mod m) 的 b），这种方法可以在 Python 3.8 中使用：

b = pow(a, -1, m)

pow 是 python-3.8 中的内置函数。在 c++ 中有类似的东西吗？

- Zhiltsoff Igor

---

这对您有帮助吗？https://stackoverflow.com/questions/53821181/what-can-i-do-on-c-to-do-an-inverse-of-a-number - Coder

请参阅此链接：C++中用于高位数的模幂运算。 - bolov

@JohnD，谢谢你，那些帖子对我很有帮助，但它们并没有回答我的问题——我在问题中强调了“内置”的特性。 - Zhiltsoff Igor

@bolov，好吧，我猜你的“不”回答了我的问题：）。唉，还是谢谢你。 - Zhiltsoff Igor

好的，我会解决这个问题。 - Coder

Answer 1

不，C++没有内置的函数（回答你的问题 :)）。

- Coder

Answer 2

是的，相对标准库boost有函数boost::integer::mod_inverse：

#include <boost/integer/mod_inverse.hpp>
#include <iostream>

using boost::integer::mod_inverse;

int main(void)
{
  int x = 3;
  int m = 5;

  int y = mod_inverse(x, m);

  std::cout << x << " ^-1 (mod " << m << ") = " << y << std::endl;;

  return 0;
}

输出：

3 ^-1 (mod 5) = 2

参考资料：

• boost::integer::mod_inverse源代码；
• boost::integer::mod_inverse文档。

请注意，如果a和m不互质，则mod_inverse(x, m)返回0，而Python的pow(x, -1, m)会引发ValueError: base is not invertible for the given modulus异常。

- Stef