我对Bigintegers的简单计算不起作用

Question

我需要计算一下:2894135 ^ 3787313 mod 4028033

正如你在下面看到的,我试图使用BigInteger因为我有非常大的数字.

import java.lang.Math;
import java.util.Scanner;
public class BigInteger extends Number implements Comparable<BigInteger>
{
  public static void main(String[] args)
  {
  BigInteger result=new BigInteger(Math.pow(2894135,3787313) % 4028033);
    System.out.println(result);
  }
}

错误:

/tmp/java_Wcf144/BigInteger.java:19:错误:BigInteger不是抽象的,并且不会覆盖抽象方法doubleValue()中的数字公共类BigInteger extends Number实现Comparable ^ /tmp/java_Wcf144/BigInteger.java:24:错误:构造函数BigInteger类中的BigInteger不能应用于给定的类型;
BigInteger结果= new BigInteger(Math.pow(2894135,3787313)%4028033); ^ required:找不到参数:double reason:实际和形式参数列表长度不同2错误

Answer 1

即使在解决错误之后你也会得到错误的答案,因为Math.pow(2894135,3787313)这将导致overflowin double并且它将返回double的最大可能值Double.MAX_VALUE.

因此,您需要在将它们转换为所有操作后进行操作BigInteger.

import java.lang.Math;
import java.util.Scanner;
import java.math.BigInteger;
public class Main
{
  public static void main(String[] args)
  {
        BigInteger a=BigInteger.valueOf(2894135);
        BigInteger b=BigInteger.valueOf(3787313);
        BigInteger m=BigInteger.valueOf(4028033);
        BigInteger result=a.modPow(b,m); //calculates a^b %m
        System.out.println(result);
  }
}

编辑: 如果你想以更优化的方式做到这一点,那么你可以使用Modular Exponentiation的概念.这将使输出O(log(exponent))变得复杂.在这里,您不能使用更大的值,因为它可能会导致overflow在long这给错误的结果结束.

码:

public class Main
{
  public static void main(String[] args)
  {
        long a=2894135;
        long b=3787313;
        long m=4028033;

        long result=modularExponentiation(a,b,m);
        System.out.println(result);
  }

    static long modularExponentiation(long a,long b,long m)
    {
        long result=1;
        while(b>0)
        {
            if(b % 2 ==1)
                result=(result * a)%m;
            a=(a*a)%m;
            b=b/2;
        }
        return result;
    }
}