c++写代码求 x mod y 的逆元。
时间: 2024-05-11 20:18:50 浏览: 15
如果需要求解 $x$ 对模 $y$ 的逆元,需要满足 $x$ 与 $y$ 互质。一个常见的求解方法是使用扩展欧几里得算法。
具体的代码实现如下:
```c
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int mod_inv(int x, int y) {
int a, b;
int d = exgcd(x, y, a, b);
if (d != 1) return -1; // 不存在逆元
return (a % y + y) % y;
}
```
其中,`exgcd` 函数是扩展欧几里得算法的实现,`mod_inv` 函数调用 `exgcd` 函数求解模数的逆元。如果不存在逆元,则返回 `-1`。
相关问题
辗转相除法求模乘逆元的c++代码
辗转相除法求模乘逆元的 C 代码如下:
```c
#include <stdio.h>
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 mod_inverse(int a, int m)
{
int x, y;
extgcd(a, m, x, y);
return (m + x % m) % m;
}
int main()
{
int a = 3, m = 11;
printf("%d 的模 %d 乘逆元为 %d\n", a, m, mod_inverse(a, m));
return 0;
}
```
以上代码使用了扩展欧几里得算法求解模乘逆元。其中,`extgcd` 函数可以求解任意两个整数的最大公约数,并返回其值,同时通过引用返回参数 `x` 和 `y` 的值,满足 $ax + by = \gcd(a, b)$。`mod_inverse` 函数则使用 `extgcd` 求解模乘逆元,即 $a$ 模 $m$ 的乘法逆元 $x$,满足 $ax \equiv 1 \pmod m$,并返回其值。
C++求模运算的乘法逆元
对于正整数a和m,如果存在一个正整数x满足ax ≡ 1 (mod m),那么我们称x为a在模m意义下的乘法逆元。如果不存在这样的x,我们则称a在模m意义下没有乘法逆元。
求模运算的乘法逆元的方法有很多,以下是其中一种方法:
使用扩展欧几里得算法求解a和m的最大公约数gcd(a,m),如果gcd(a,m)>1,说明a在模m意义下没有乘法逆元;
如果gcd(a,m)=1,那么根据扩展欧几里得算法的推论,可以求解出一组整数x和y,使得ax+my=gcd(a,m)=1;
因为ax ≡ 1 (mod m),所以ax ≡ 1 + km,其中k是一个整数;
因此,x ≡ (1 + km)/a (mod m),其中k可以是任意整数,但是为了保证x在模m意义下的值最小,一般取k使得x的值在0~m-1之间。具体地,可以先计算(1 + km)%m,然后再计算 (1 + km)/a mod m。
以上就是求模运算的乘法逆元的基本方法。在实际计算中,可以预处理出所有1~m-1之间的整数在模m意义下的乘法逆元,存储在一个数组中,在需要使用时直接查表就可以了。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)