华师一附中OI组

标题: (重载)高精度任意数快速幂 [打印本页]
作者: Settwarl    时间: 2014-12-23 19:19
标题: (重载)高精度任意数快速幂
支持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. }

  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. }
复制代码






欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2