<分区>
晚上好。 我已经编写了代码来计算斐波那契数的余数 n 和模 m,但结果是在 n=100000 之后给我负余数,在此之前一切都很好。在使用 Long 之前,我使用 BigInteger 代替:但是,具有这种变量类型的代码非常慢。我还使用 Q 矩阵和平方求幂。 这是代码:
import java.util.Scanner;
class Main {
private void bigfib(){
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long m = sc.nextLong();
long [][] a = new long[][]{{1,1},{1,0}};
System.out.println(pow(a,n)[0][1]%m);
}
private long[][] mult(long[][] m1, long[][] m2) {
long a11 = m1[0][0]*m2[0][0] + m1[0][1]*m2[1][0];
long a12 = m1[0][0]*m2[0][1] + m1[0][1]*m2[1][1];
long a21 = m1[1][0]*m2[0][0] + m1[1][1]*m2[1][0];
long a22 = m1[1][0]*m2[0][1] + m1[1][1]*m2[1][1];
long[][] mResult = new long[][]{{a11,a12},{a21,a22}};
return mResult;
}
private long [][] pow(long a[][], long p) {
long[][] result;
if (p==1)
return a;
if (p==2)
return mult(a,a);
if (p%2==1){
return mult(a,pow(a,p-1));
}
else{
result = pow(a,p/2);
return mult(result,result);
}
}
public static void main(String[] args) {
new Main().bigfib();
}
有人能告诉我,为什么余数开始为负,没有 BigItegers 如何解决这个问题?