用Java写快速幂求逆元
时间: 2023-06-30 17:08:46 浏览: 65
快速幂求逆元是一个常见的数学问题,可以用于模数为质数的情况下求解除法的结果。下面是一个用Java实现的快速幂求逆元的代码示例:
```java
public static long modInverse(long a, long p) {
// 求a关于p的逆元
long ans = 1;
long base = a;
while (p > 0) {
if ((p & 1) == 1) {
ans = (ans * base) % p;
}
base = (base * base) % p;
p >>= 1;
}
return ans;
}
```
其中,`a`是需要求逆元的数,`p`是模数。这段代码使用了快速幂算法,通过不断对`a`进行平方运算和取模运算,来快速求出`a`关于`p`的逆元。
相关问题
C语言快速幂和快速幂求逆元
快速幂是一种用于快速计算一个数的整数次幂的算法,其时间复杂度为O(logn)。而快速幂求逆元是在模意义下,求一个数的乘法逆元的算法,其时间复杂度也为O(logn)。
以下是C语言实现快速幂和快速幂求逆元的代码:
1. 快速幂
```c
#include <stdio.h>
typedef long long LL;
// a^k % p
int qmi(int a, int k, int p) {
int res = 1;
while (k) {
if (k & 1) res = (LL)res * a % p;
k >>= 1;
a = (LL)a * a % p;
}
return res;
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
int a, k, p;
scanf("%d%d%d", &a, &k, &p);
printf("%d\n", qmi(a, k, p));
}
return 0;
}
```
2. 快速幂求逆元
```c
#include <stdio.h>
typedef long long LL;
// a^k % p
int qmi(int a, int k, int p) {
int res = 1;
while (k) {
if (k & 1) res = (LL)res * a % p;
k >>= 1;
a = (LL)a * a % p;
}
return res;
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
int a, p;
scanf("%d%d", &a, &p);
int res = qmi(a, p - 2, p); // a^(p-2)
if (a % p) printf("%d\n", res); // 不是倍数,输出结果
else puts("impossible"); // 是倍数,不存在逆元
}
return 0;
}
```
java有限域求乘法逆元
以下是Java中有限域求乘法逆元的示例代码:
```java
public static int getInverse(int a, int p) {
int[] xy = extendedEuclidean(a, p);
if (xy[0] != 1) {
throw new ArithmeticException("Inverse does not exist");
}
return (xy[1] + p) % p;
}
public static int[] extendedEuclidean(int a, int b) {
if (b == 0) {
return new int[] {a, 1, 0};
}
int[] xy = extendedEuclidean(b, a % b);
int x = xy[2];
int y = xy[1] - (a / b) * xy[2];
return new int[] {xy[0], x, y};
}
```
其中,`getInverse`方法用于计算乘法逆元,`extendedEuclidean`方法用于计算扩展欧几里得算法。在有限域GF(p)中,a的乘法逆元为b,当且仅当a和p互质,即gcd(a, p) = 1。