algo-aha

求a^b mod 1337

• https://leetcode.com/problems/super-pow/

b是各位数字存在数组中的大数

int superPow(int a, vector<int>& b) {
    // 幂太大，将幂分解。
    // 例如，37^213 mod K = 37^(210+3) mod K 
    //   = ((37^21 mod K)^10 mod K) * (37^3 mod K)
    if (b.empty()) return 1;
    const int K = 1337;
    int lastDigit = b.back(); b.pop_back();        
    return (pow(superPow(a, b), 10, K) * pow(a, lastDigit, K)) % K;
}

// 幂较小用该函数计算，a^b mod K
int pow(long a, int b, int K) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % K;
        a = (a * a) % K;
        b >>= 1;
    }
    return ans;
}

不用*、/，只用+、-、移位作两正数相乘

int minProduct(int a, int b) {
    if (a > b) swap(a, b);
    return rMinProduct(a, b);
}

int rMinProduct(int small, int big) {
    if (small == 0) return 0;
    if (small == 1) return big;

    int halfProd = rMinProduct(small >> 1, big);
    int prod = halfProd << 1;
    if (small & 1) prod += big;

    return prod;
}