快速幂

递归快速幂

//递归快速幂 
ll qpow(int a,int n) {
	if(n == 0) {
		return 1;	
	}
	else if (n%2 == 1) {
		return qpow(a,n-1) * a;
	}else {
		long long temp = qpow(a,n/2);
		return temp*temp;
	}
	
}

非递归快速幂

ll quick_pow(int a,int n) {
    int res = 1;
    while(n) {
        if(n & 1 == 1) {
            res*=a;
        }
        n>>=1;
        a*=a;
    }
    return res;
}