23 lines
616 B
C++
23 lines
616 B
C++
#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;
|
||
} |