java - 给定系列中总和的最后 10 位数字

Question

输入包含一个整数N

这个系列看起来像这样

这是来自 hackerrank 的问题，我的代码通过了所有测试用例，除了超时，实际上非常感谢您的帮助

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
 public class Solution {
     public static BigInteger calculateSelfPowers(){
         Scanner z = new Scanner(System.in);
         int num = z.nextInt();
         BigInteger modval = BigInteger.valueOf(10).pow(10);
         BigInteger sum = BigInteger.ZERO;
         for (int i = 1; i <= num; i++)
         sum = sum.add(BigInteger.valueOf(i).modPow(BigInteger.valueOf(i), modval)).mod(modval);
         return sum;
     }
     public static void main(String[] args){
         System.out.println(calculateSelfPowers());
     }

 }

这里是 hackerrank 中问题的链接 linkhere

Answer 1

您可以通过将 mod() 移出循环并仅调用 BigInteger.valueOf(i) 一次来改进代码。加法成本低(速度快)，而 mod() 则不然。最终的总和可能是 16 或 17 位数字，但您可以使用 mod() 一次来获得与代码中 mod() 不断减少的结果相同的结果。

这个简单的示例(我删除了扫描仪并获取了允许的最高数字，999999)在我的系统上仅运行了 4 秒:

package modpowtest;

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;

public class ModPowTest 
{
    public static BigInteger calculateSelfPowers()
    {
        int num = 999999;
        BigInteger modval = BigInteger.valueOf(10).pow(10);
        BigInteger sum = BigInteger.ZERO;
        for (int i = 1; i <= num; i++)
        {
            BigInteger bi = BigInteger.valueOf(i); 
            sum = sum.add(bi.modPow(bi, modval));
        }
        return sum.mod(modval);
    }

    public static void main(String[] args)
    {
        System.out.println(calculateSelfPowers());
    }

}

您只需再次添加 Scanner 内容并将其重命名为 Solution。

如果我使用num = 10;，我会得到与他们相同的解决方案。