This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
#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;
