快速冪_2017 NOIP普及組 程序填空第1題
2023-07-31 21:08 作者:windowsxpw | 我要投稿
#include<bits/stdc++.h>
#define int unsigned long long
#pragma GCC optimize(2)
using namespace std;
int fastPower(int base, int exponent) {
? ? if (!exponent) {
? ? ? ? return 1;
? ? } else if (exponent==1) {
? ? ? ? return base;
? ? } else {
? ? ? ? long long half = fastPower(base, exponent>>1);
? ? ? ? if (!(exponent&1)){
? ? ? ? ? ? return half * half;
? ? ? ? } else {
? ? ? ? ? ? return half * half * base;
? ? ? ? }
? ? }
}
signed main(){
? ? int a,b;
? ? cin>>a>>b;
? ? cout<<fastPower(a,b);
? ? return 0;
}
雖說(shuō)遞歸但還是o(logn)
標(biāo)簽：
