1. a ^ b : 题链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
a ^ b = 
a * a * a * a * a .....
把 指数b 化作二进制  = 
a ^ 1 * a ^ 2 * a ^ 4 ....


// 例如: 求 m^k % p
public static int qmi(int m, int k, int p){
	int res = 1, t = m;
	while(k > 0){
		if( (k&1) == 1){
			res = res * t % p;
		}
		t = t * t % p;  //t^1 t^2 t^4 ...
		k = k>>1;
	}
	return res % p;
}

2. a * b : 题链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
a * b = 
a + a + a + a + a .....
把 指数b 化作二进制  = 
a * 1 + a * 2 + a * 4 ....


// 例如: 求 m*k % p
public static int qci(int m, int k, int p){
	int res = 0, t = m;
	while(k > 0){
		if((b&1) == 1) res = (res + t) % p;
        t = (t * 2) % p;
        b >>= 1;
	}
	return res % p;
}