求m的n次方

不考虑高精度，一般有三种做法：

最笨的做法是把m连乘n-1次，这个就不写了。

第二种做法很好理解，是递归的快速幂，当n是偶数时，分解成两个n/2次方然后再乘起来，n是奇数的时候分解成两个n/2次方乘起来再多乘一个m；

第三种做法有点难得理解，是将n化成二进制，然后把1的那些数位乘起来；

经过测试，n很大的时候，还是第三种方法快。

[cpp]  view plain  copy

1. #include <iostream>  
2. using namespace std;  
3. int a,b;  
4. long long way1(int n)  
5. {  
6.    if (n==0) return 1;   //0次方等于1  
7.    else if (n%2==1) return way1(n/2)*way1(n/2)*a; //奇数次  
8.         else return way1(n/2)*way1(n/2);//偶数次  
9. }  
10. long long way2(int n)  
11. {  
12.     long long s=1,t=a;  
13.     while (n>0)  
14.     {  
15.         if (n%2==1) s=(s*t);  
16.         n=n/2;t=t*t;  
17.     }  
18.     return s;  
19. }  
20. int main()  
21. {  
22.     a=2;b=50;cout<<way1(b)<<' '<<way2(b);  
23.     return 0;  
24. }