我想将这个函数代码重写为java中的BigInteger类:
static int power(int x, int y, int p)
{
int res = 1; // Initialize result
while (y > 0) {
// If y is odd, multiply x with result
if ((y & 1) != 0)
res = res * x;
// y must be even now
y = y >> 1; // y = y/2
x = x * x; // Change x to x^2
}
return res % p;
}
我尝试并编写了以下代码:
static BigInteger power(BigInteger x, BigInteger y, BigInteger p) {
BigInteger res = BigInteger.ONE; // Initialize result
while (y.compareTo(BigInteger.ZERO) == 1) {
// If y is odd, multiply x with result
if ((y.and(BigInteger.ONE)) != BigInteger.ZERO)
res = res.multiply(x);
// y must be even now
y = y.shiftRight(1); // y = y/2
x = x.multiply(x); // Change x to x^2
}
return res.mod(p);
}
但是当我测试例如输入“power(2, 5, 13)”时,输出是11,但正确答案是6。
我写的代码检查了好几遍,都找不到问题所在。你能帮我输出正确的答案代码吗?
BigInteger.modPow(BigInteger, BigInteger)
。我会这样称呼它,比如
static BigInteger power(BigInteger x, BigInteger y, BigInteger p) {
return x.modPow(y, p);
}
其次,您无法使用三个
int
值调用该方法。你需要BigInteger
参数。就像,
public static void main(String[] args) {
System.out.println(power(BigInteger.valueOf(2),
BigInteger.valueOf(5),
BigInteger.valueOf(13)));
}
我明白了
6