逆元代码
时间: 2023-07-02 09:14:45 浏览: 74
以下是求逆元的代码实现:
```python
def mod_inverse(a, m):
"""
求 a 在模 m 意义下的逆元
"""
def extended_euclidean_algorithm(a, b):
if b == 0:
return 1, 0, a
else:
x, y, gcd = extended_euclidean_algorithm(b, a % b)
x, y = y, x - (a // b) * y
return x, y, gcd
x, y, gcd = extended_euclidean_algorithm(a, m)
if gcd != 1:
raise ValueError('a 和 m 不互质')
else:
return x % m
```
其中 `a` 和 `m` 分别是待求逆元的数和模数,函数返回 `a` 在模 `m` 意义下的逆元。如果 `a` 和 `m` 不互质,则会抛出 `ValueError` 异常。
相关问题
计算逆元附上示例代码和解释
好的,关于计算逆元,我可以给你一些简单的解释和示例代码。
在数论中,逆元是一个元素在某个运算下的倒数,即它与另一个元素相乘等于这个运算下的单位元素。在模运算下,逆元的计算方法可以用扩展欧几里得算法来实现。
以下是一个使用Python实现的计算逆元的示例代码:
```python
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
else:
gcd, x1, y1 = extended_gcd(b, a % b)
x, y = y1, x1 - (a // b) * y1
return gcd, x, y
def mod_inverse(a, m):
gcd, x, y = extended_gcd(a, m)
if gcd != 1:
raise ValueError('No inverse exists')
else:
return x % m
```
这个函数接受两个参数a和m,返回a在模m下的逆元。其中,extended_gcd函数实现了扩展欧几里得算法,用于计算最大公约数和逆元。如果a没有逆元,将会抛出异常。
希望这对你有所帮助。
c++组合数(逆元)代码
```cpp
const int MAXN = 1e6 + 5;
const int MOD = 998244353;
int fac[MAXN], inv[MAXN];
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % MOD;
a = 1ll * a * a % MOD;
b >>= 1;
}
return res;
}
void init() {
fac[0] = 1;
for (int i = 1; i < MAXN; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
inv[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2);
for (int i = MAXN - 2; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
}
int C(int n, int m) {
return n < m ? 0 : 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
```
相关推荐
![](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)