如何使用java计算极大指数数的余数？

Question

如何使用java计算极大指数数的余数？例如.(48 ^ 26)/ 2401

我尝试使用BIGINTEGER,但它为大除数提供相同的输出.我不确定BIG INTEGER是否可以做到这一点.我已经尝试了所有其他PRIMITIVE数据类型.他们似乎不够.

仅供参考,它尝试了以下代码:

BigInteger a = new BigInteger("48");
a = a.pow(26);
BigInteger b = new BigInteger("2401");//49*49
a = a.mod(b);
System.out.println(a);

我不知道为什么我每次都得到相同的输出,现在工作正常,这很奇怪.答案是1128

Answer 1

您可以使用较小数字的重复模数.

说你有

(a * b) % n
((A * n + AA) * (B * n + BB)) % n                     | AA = a %n & BB = b % n
(A * B * n^2 + A * N * BB + AA * B * n + AA * BB) % n
AA * BB % n                                           since x * n % n == 0
(a % n) * (b % n) % n

在你的情况下,你可以写

48^26 % 2401
(48^2) ^ 13 % 2401

如

int n = 48;
for (int i = 1; i < 26; i++)
    n = (n * 48) % 2401;
System.out.println(n);

int n2 = 48 * 48;
for (int i = 1; i < 13; i++)
    n2 = (n2 * 48 * 48) % 2401;
System.out.println(n2);

System.out.println(BigInteger.valueOf(48).pow(26).mod(BigInteger.valueOf(2401)));

版画

1128
1128
1128

正如@Ruchina指出的那样,你的例子足够小,可以用一个简单的双重表达来计算.

for (int i = 1; i < 100; i++) {
    BigInteger mod = BigInteger.valueOf(48).pow(i).mod(BigInteger.valueOf(2401));
    double x = Math.pow(48, i) % 2401;
    if (mod.intValue() != x) {
        System.out.println(i + ": " + mod + " vs " + x);
        break;
    }
}

版画

34: 736 vs 839.0

换句话说,任何48的幂都可以达到33.