如何使用 java 计算极大指数数的余数?
例如。 (48^26)/2401
我尝试使用 BIGINTEGER,但是它为大除数提供了相同的输出。我不确定 BIGINTEGER 是否可以做到这一点。我尝试了所有其他 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
您可以使用较小数字的重复模数。
说你有
(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
as
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)));
prints
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;
}
}
prints
34: 736 vs 839.0
换句话说,48 的任何幂都可以达到 33。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)