给定两个整数 A 和 M，让我们找到 A 在模 M 下的模乘逆元。
模乘逆元是指一个整数 X，满足：
> A X ≡ 1 (mod M)
Try it on GfG Practice<img src="https://www.geeksforgeeks.org/problems/modular-multiplicative-inverse-1587115620/1" alt="redirect icon" />
注意： X 的值应该在范围 {1, 2, … M-1} 内，即在整数模 M 的范围内。（请注意 X 不能为 0，因为 A*0 mod M 永远不会是 1）。当且仅当 A 和 M 互质（即 gcd(A, M) = 1）时，“A modulo M”的乘法逆元才存在。
示例：
> 输入： A = 3, M = 11
> 输出： 4
> 解释： 因为 (4*3) mod 11 = 1，所以 4 是 3（在 11 下）的模逆元。
> 有人可能会认为 15 也是一个有效的输出，因为 "(15*3) mod 11" 也是 1，但 15 不在范围 {1, 2, … 10} 内，因此是无效的。
>
> 输入： A = 10, M = 17
> 输出： 12
> 解释： 因为 (10*12) mod 17 = 1，所以 12 是 10（在 17 下）的模逆元。
朴素方法： 为了解决这个问题，我们可以遵循以下思路：
> 一个朴素的方法是尝试从 1 到 m 的所有数字。对于每一个数字 x，检查 是否等于 1。
下面是上述方法的实现：
C++
CODEBLOCK_9811bc25
Java
CODEBLOCK_8380ec1e
Python
CODEBLOCK_b48b70bd
C#
CODEBLOCK_d085a979
JavaScript
CODEBLOCK_0a52d031
PHP
CODEBLOCK_0de437ca
Output
4
时间复杂度： O(M)
辅助空间： O(1)
> 我们可以使用扩展欧几里得算法，该算法接受两个整数 ‘a‘ 和 ‘b‘，然后找到它们的 gcd，并且也能找到满足下式的 ‘x‘ 和 ‘y‘：
>
> ax + by = gcd(