快速幂

设a,b,c都是正整数，计算a的b次方对c取模（a ^ b % c）在非对称密钥算法RSA中是一个很基本的问题，由于a,b,c可能会比较大，直接计算显然无法满足效率要求，可以借鉴快速幂的思想减少计算次数。
做法是根据b的奇偶性，分情况讨论：

如果b为偶数，不妨设b = 2k，那么

a ^ b % c  
= a ^ 2k % c  
= (a ^ k % c) * (a ^ k % c) % c  
= (a ^ k % c) ^ 2 % c

如果b为奇数， 不妨设b = 2k + 1，那么

a ^ b % c  
= (a * a ^ 2k) % c  
= (a % c) * (a ^ 2k % c) % c  
= (a % c) * ((a ^ k % c) ^ 2 % c) % c

可见，无论奇偶，计算规模都可以缩至原来的一半，时间复杂度由O(b)降至O(logb)。

根据以上递推式，很容易写出解决该问题的递归算法。

int powmod(int a, int b, int c) {
    if (0 == b) return 1;
    long long x = powmod(a, b/2, c);
    x = x * x % c;
    if (b & 1) x = x * a % c;
    return x;
}

如果将实现改成迭代方式就是这样：

int powmod(int a, int b, int c) {
    long long x = 1, t = a;
    while (b) {
        if (b & 1) x = x * t % c;
        t = t * t % c;
        b /= 2;
    }
    return x;
}