java - 如何获得2次幂的最后一位

Question

我正在解决一个要求获得 2^1001 的最后 100 位数字的问题。解决方案必须在 java 中并且不使用 BigInteger，仅使用 int 或 Long。目前我想创建一个处理 100 位数字的类。所以我的问题是，是否有另一种方法可以使用 int 或 long 处理溢出来获得 100 位数字。

谢谢大家。

Answer 1

已编辑：我的模运算符中的 10 次幂（哎呀）

2^1001 的最后 100 位数字是数字 2^1001（模 10^100）。

请注意，2^1001 (mod 10^100) = 2*(2^1000(mod 10^100)) (mod 10^100)。

查看模数的属性：http: //www.math.okstate.edu/~wrightd/crypt/lecnotes/node17.html

这是 99% 的数学问题，1% 的编程问题。:)

但是，使用这种方法，您将无法仅使用整数，因为 10^100 不适合 int 或 long。

但是，您可以使用它来查找 2^1001 的最后 10 位，然后使用单独的例程来查找接下来的 10 位等，其中每个例程都使用此功能...

Answer 2

最快的方法（编码明智）是创建一个由 100 个整数组成的数组，然后有一个函数从一个位置开始并将每个数字加倍。确保取模数 10 并在需要时结转 1s。对于第 100 位，只需消除结转。做 1001 次，你就完成了。