[算法]高精度快速幂

 1 /**高精度快速幂*/
 2 #include<iostream>
 3 #include<cstring> 
 4 using namespace std;
 5 int result[1005]={1,0},base[1005],tmp[1005];
 6 int n;//指数
 7 int size=500;//size为结果result的1/2，因为得下面函数用到的下标[i+j] 
 8 int mul(){//高精度乘法 
 9     int i,j;
10     memset(tmp,0,sizeof(tmp));//将数组tmp初始化为0
11     for(i=0;i<size;i++){//先存放相乘得到的结果，暂时不处理进位 
12         for(j=0;j<size;j++){
13             tmp[i+j]+=result[i]*base[j];
14         }
15     }
16     for(i=0;i<size;i++){//处理进位 
17         for(j=0;j<size;j++){
18             tmp[i+j+1]+=tmp[i+j]/10;
19             tmp[i+j]%=10;
20         }
21     }
22     memcpy(result,tmp,sizeof(tmp));//将tmp数组复制到result中 
23 }
24 int myPow(){//base*base，和mul函数差不多，只改了一点点 
25     int i,j;
26     memset(tmp,0,sizeof(tmp));
27     for(i=0;i<size;i++){
28         for(j=0;j<size;j++){
29             tmp[i+j]+=base[i]*base[j];
30         }
31     }
32     for(i=0;i<size;i++){
33         for(j=0;j<size;j++){
34             tmp[i+j+1]+=tmp[i+j]/10;
35             tmp[i+j]%=10;
36         }
37     }
38     memcpy(base,tmp,sizeof(tmp));
39 }
40 
41 int main(){
42     int i,j;
43     int t;
44     cin>>t>>n;//输入底和指数 
45     for(i=0;t;i++){//将接收的底放入数组base 
46         base[i]=t%10;
47         t=t/10;
48     }
49     while(n){
50         if(n&1){
51             mul();
52         }
53         n=n>>1;
54         myPow();
55     } 
56     int flag=0;
57     for(i=2*size-1;i>=0;i--){
58         if(flag==1){
59             cout<<result[i]; 
60         }
61         if(flag==0&&result[i]!=0){
62             flag=1;
63             cout<<result[i];
64         }
65     } 
66     return 0;
67 }