java - 对值 1 到 n 的一系列 n^n 求和且不会溢出？只需要答案的最后一位数字

Question

我想编写一个 Java 程序，对从 1 到 n 的所有整数 n^n 求和。我只需要这个数字的最后 10 位数字，但给定的 n 值超过了 800。

我已经编写了一个基本的java程序来计算这个，并且对于n < 16它工作得很好。但它显然不能处理这么大的数字。我想知道是否有一种方法可以收集通常会溢出 long 的数字的最后 10 位数字，如果是的话，该方法或技术可能是什么。

我没有代码可以展示，只是因为我已经编写的代码正是您所期望的。一个在 i<=n 时运行 i*i 的 for 循环，以及一个将每次迭代与之前的迭代相加的计数器。有用。我只是不知道如何解决更大数量的问题，并且需要指导。

n=16 左右，数字会溢出 long，并返回负值。 BigInteger 会对此有所帮助吗？还是这种数据类型仍然太小？或者有人可以向我指出一种收集大量数字的最后 10 位数字的技术吗？我可以将它存储在一个数组中，然后将它们求和(如果我能做到这一点)。

无论如何，我不期望有一段完整的代码，但也许有一些关于如何重新看待这个问题的建议？我的n00b self 缺少一些技巧吗？

谢谢!

Answer 1

sums all the integers n^n from 1 through n. I only need the last 10 digits of this number

如果您只需要最后 10 位数字，则意味着您需要 sum % 10¹⁰。

总和为11 + 22 + 33 + ... nⁿ。

根据equivalences规则:

(a + b) % n = [(a % n) + (b % n)] % n

因此，您需要计算 iⁱ % 101⁰，对于 i=1 到 n，对它们求和，并对总和执行最后一个模。

根据modular exponentiation在维基百科上的文章中，有一些有效的方法可以在计算机上计算 aⁱ % m。你应该阅读这篇文章。

但是，如article also says :

Java's java.math.BigInteger class has a modPow() method to perform modular exponentiation

将所有这些结合到 Java 中的高效实现中，不会使用过多的内存:

static BigInteger calc(int n) {
    final BigInteger m = BigInteger.valueOf(10_000_000_000L);
    BigInteger sum = BigInteger.ZERO;
    for (int i = 1; i <= n; i++) {
        BigInteger bi = BigInteger.valueOf(i);
        sum = sum.add(bi.modPow(bi, m));
    }
    return sum.mod(m);
}

或者使用流相同:

static BigInteger calc(int n) {
    final BigInteger m = BigInteger.valueOf(10).pow(10);
    return IntStream.rangeClosed(1, n).mapToObj(BigInteger::valueOf).map(i -> i.modPow(i, m))
                    .reduce(BigInteger.ZERO, BigInteger::add).mod(m);
}

测试

System.out.println(calc(800)); // prints: 2831493860