1
2
3
4
5
6
7
8
9
10
11
| int pow(int a, int n) {
if(n == 0) return 1;
boolean positive = n < 0 ? true : false;
int res = 1;
while(n > 0) {
if(n % 2 != 0)
res *= a;
a *= a;
n >>= 1;
}
}
|
1
2
3
4
5
6
7
8
9
10
| private void muti(int[][] a, int[][] b, int[][] c, int m) {
int t00 = (a[0][0]*b[0][0] + a[0][1]*b[1][0]) % m;
int t01 = (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % m;
int t10 = (a[1][0]*b[0][0] + a[1][1]*b[1][0]) % m;
int t11 = (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % m;
c[0][0] = t00;
c[0][1] = t01;
c[1][0] = t10;
c[1][1] = t11;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| private int fib(int n, int m) {
if(n == 0) return 0;
else if(n <= 2) return 1;
int[][] b = {{1,1},{1,0}}, res = {{1,0},{0,1}};
n -= 2;
while(n > 0) {
if(n % 2 != 0)
muti(b,res,res,m);
muti(b,b,b,m);
n /= 2;
}
return (res[0][0] + res[0][1]) % m;
}
|
参考资料
求斐波那契(Fibonacci)数列通项的七种实现方法