java - 变量太大的数字

Question

我要找出 1^1 + 2^2 + 3^3.. + 1000^1000 的最后十位数字。有什么办法可以用纯逻辑找出答案吗？我认为您无法存储那么大的数字。

这道题来自数学竞赛，但我想尝试用 Java 来做这道题。

Answer 1

你不需要存储那么大的数字，你只需要最后十位数字。您可以将其长期存储。

计算大幂的有效方法是乘以平方，例如19^19 = 19 * 19^2 * 19 ^ 16 = 19 * 19 ^ 2 * 19^2^2^2^2。当您的值大于 10^10 时，您可以截断最后 10 位数字。

顺便说一句，1000^1000 的最后十位数字是 0000000000，当您将其添加到您的总和中时，它与添加零相同；)

---

编辑:虽然您不必使用 BigInteger，但编写起来更简单。

BigInteger tenDigits = BigInteger.valueOf(10).pow(10);
BigInteger sum = BigInteger.ZERO;
for (int i= 1; i <= 1000; i++) {
    BigInteger bi = BigInteger.valueOf(i);
    sum = sum.add(bi.modPow(bi, tenDigits));
}
sum = sum.mod(tenDigits);

modPow 比单独使用 mod 的 pow 更有效，因为它不需要计算非常大的数字，只需计算修改。