(重载)高精度任意数快速幂

Settwarl

支持5万位。用运算符重载实现。

1. #include<iostream>
   
2. #include<cstring>
   
3. #include<cstdio>
   
4. using namespace std;
   
5. const int MAXL=50000;
   
6. struct SClong
   
7. {
   
8.     int len,s[MAXL];
   
9.     SClong(){len=1;memset(s,0,sizeof(s));}
   
10.     SClong operator=(const char* num)
    
11.     {
    
12.         len=strlen(num);
    
13.         for(int i=1;i<=len;i++)s[i-1]=num[len-i]-'0';
    
14.         return *this;
    
15.     }
    
16.     SClong operator=(int num)
    
17.     {
    
18.         char a[MAXL];
    
19.         sprintf(a,"%d",num);
    
20.         *this=a;
    
21.         return *this;
    
22.     }
    
23.     SClong(const char* num){*this=num;}
    
24.     SClong(int num){*this=num;}
    
25.     SClong operator+(const SClong &num)
    
26.     {
    
27.         SClong c;
    
28.         c.len=max(len,num.len)+1;
    
29.         for(int i=0;i<c.len;i++)
    
30.         {
    
31.             c.s[i]=c.s[i]+s[i]+num.s[i];
    
32.             c.s[i+1]+=c.s[i]/10;
    
33.             c.s[i]%=10;
    
34.         }
    
35.         if(c.s[c.len-1]==0)--c.len;
    
36.         return c;
    
37.     }
    
38.     SClong operator+=(const SClong &num)
    
39.     {
    
40.          *this=*this+num;
    
41.          return *this;
    
42.     }
    
43.     SClong operator*(const SClong &num)
    
44.     {
    
45.         SClong c;
    
46.         c.len=len+num.len;
    
47.         for(int i=0;i<len;i++)
    
48.             for(int j=0;j<num.len;j++)
    
49.             {
    
50.                 c.s[i+j]=c.s[i+j]+s[i]*num.s[j];
    
51.                 c.s[i+j+1]+=c.s[i+j]/10;
    
52.                 c.s[i+j]=c.s[i+j]%10;
    
53.             }
    
54.         if(c.s[c.len-1]==0)--c.len;
    
55.         return c;
    
56.     }
    
57.     SClong operator*=(const SClong &num)
    
58.     {
    
59.         *this=*this*num;
    
60.         return *this;
    
61.     }
    
62. };
    
63. ostream &operator<<(ostream&out,const SClong&num)
    
64. {
    
65.     for(int i=num.len-1;i>=0;--i)cout<<num.s[i];
    
66. }
    
67. istream &operator>>(istream&in, SClong&num)
    
68. {
    
69.     char n[MAXL];
    
70.     in>>n;
    
71.     num=n;
    
72.     return in;
    
73. }
    
74. SClong exp(SClong a,int t)
    
75. {
    
76.     SClong ans=1,base=a;
    
77.     while(t>0)
    
78.     {
    
79.         if(t%2)ans*=base;
    
80.         t/=2;
    
81.         base*=base;
    
82.     }
    
83.     return ans;
    
84. }
    
85. 
    
86. int main()
    
87. {
    
88.     SClong m;
    
89.     int n;
    
90.     while(true)
    
91.     {
    
92.         cin>>m>>n;
    
93.         cout<<exp(m,n);
    
94.         cout<<endl<<endl;
    
95.     }
    
96.     return 0;
    
97. }
    

复制代码