python/TangDou/AcWingSuanFaJinJieZhiNan/qmi.cpp

#include <bits/stdc++.h>

using namespace std;
// https://www.jianshu.com/p/749b6ee1d001
//栗子： 2^11 = 2 ^ (1011)2
//就是把11拆成二进制数位，然后从右到左进行次方base的迭乘
//在从右到左的枚举过程中，发现本位是1,就乘上本位的base
//原来需要2*2*...*2，共10次，即O(N)
//现在需要log以2为底11就是log_2{11} 即4次
int qmi(int a, int k) {
    int ans = 1;
    while (k) {
        if (k & 1) ans *= a;
        a *= a; //次方base
        k >>= 1;
    }
    return ans;
}

int main() {
    cout << qmi(2, 11) << endl;
    return 0;
}