快速幂(c++题解)

题目描述

我们通常把a的b次方记作a^b，为了方便，我们经常直接使用C++内置函数pow(a,b)来完成这个工作，但a的b次方就是把a垒乘b次，时间复杂度为O(b)，当b值很大时，将会耗去大量时间，所以请同学们不能再偷懒了，直接写一个快速幂函数记作qkpow(a,b)

本题需要你求出2的n次方(n<63)

输入格式

一个非负整数n(n<63)

输出格式

输出2^n次方的结果

样例

样例输入

复制62

样例输出

复制4611686018427387904

非常神奇暴力过了，不要模仿： 

#include <bits/stdc++.h>
using namespace std;
int n;
long long m[10000005],x=1;
int main(){cin>>n;for(int i=1;i<=n;i++){x*=2;}cout<<x;
}

_____________________________________________________________________________

写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

_____________________________________________________________________________

正常代码： 

#include <bits/stdc++.h>
using namespace std;
int a,b,c;
long long f(long long n){if(n==1)return 2;if(n==0)return 1;long long x=f(n/2);if(n%2==0)return x*x;else return 2*x*x;
}
int main() { cin>>a;cout<<f(a);
}