// 递归快速幂: 
int pow(int a, int b) {
    if(b == 0)
    	return 1;
    else if(b == 1)
    	return a;
    else {
    	int x = pow(a, b/2);
    	if(b % 2 == 1)
    	    return x * x * a;
    	else
    	    return x * x;
    }
}


// 非递归快速幂: 把幂次转换为二进制，例如求a11，把11转换为二进制1011，即可以把a11理解为a8×a2×a1
long long pow(long long a, long long b) {
    long long sum = 1;
    int rest = b; 
    int squ = a;
    while (rest != 0) {
        int remainder = rest % 2;
        rest = rest / 2;
        if (remainder) sum = sum * squ;
        squ = squ * squ;
    }
    return sum;
}