C++ 大数模板

适合我这种不会java的SB
没有大数%大数
  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <algorithm>
  4 #include <string.h>
  5 using namespace std;
  6 /*
  7 * 完全大数模板
  8 * 输出cin>>a
  9 * 输出a.print();
 10 * 注意这个输入不能自动去掉前导0的，可以先读入到char数组，去掉前导0，再用构造函数。
 11 */
 12 #define MAXN 9999
 13 #define MAXSIZE 1010
 14 #define DLEN 4
 15 class BigNum
 16 {
 17     private:
 18     int a[5000]; //可以控制大数的位数
 19     int len;
 20     public:
 21      BigNum(){len=1;memset(a,0,sizeof(a));} //构造函数
 22      BigNum(const int); //将一个int类型的变量转化成大数
 23      BigNum(const char*); //将一个字符串类型的变量转化为大数
 24      BigNum(const BigNum &); //拷贝构造函数
 25      BigNum &operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算
 26      friend istream& operator>>(istream&,BigNum&); //重载输入运算符
 27      friend ostream& operator<<(ostream&,BigNum&); //重载输出运算符
 28      BigNum operator+(const BigNum &)const; //重载加法运算符，两个大数之间的相加运算
 29      BigNum operator-(const BigNum &)const; //重载减法运算符，两个大数之间的相减运算
 30      BigNum operator*(const BigNum &)const; //重载乘法运算符，两个大数之间的相乘运算
 31      BigNum operator/(const int &)const; //重载除法运算符，大数对一个整数进行相除运算
 32      BigNum operator^(const int &)const; //大数的n次方运算
 33 
 34      int operator%(const int &)const; //大数对一个int类型的变量进行取模运算
 35      BigNum operator% (const BigNum &)const;
 36      bool operator>(const BigNum &T)const; //大数和另一个大数的大小比较
 37      bool operator>(const int &t)const; //大数和一个int类型的变量的大小比较
 38      void print(); //输出大数
 39 };
 40 
 41 BigNum::BigNum(const int b) //将一个int类型的变量转化为大数
 42 {
 43    int c,d=b;
 44    len=0;
 45    memset(a,0,sizeof(a));
 46    while(d>MAXN)
 47    {
 48    c=d-(d/(MAXN+1))*(MAXN+1);
 49    d=d/(MAXN+1);
 50    a[len++]=c;
 51    }
 52  a[len++]=d;
 53 }
 54 
 55 BigNum::BigNum(const char *s) //将一个字符串类型的变量转化为大数
 56 {
 57    int t,k,index,L,i;
 58    memset(a,0,sizeof(a));
 59    L=strlen(s);
 60    len=L/DLEN;
 61    if(L%DLEN)len++;
 62    index=0;
 63    for(i=L-1;i>=0;i-=DLEN)
 64    {
 65    t=0;
 66    k=i-DLEN+1;
 67    if(k<0)k=0;
 68    for(int j=k;j<=i;j++)
 69    t=t*10+s[j]-'0';
 70    a[index++]=t;
 71    }
 72 }
 73 
 74 BigNum::BigNum(const BigNum &T):len(T.len) //拷贝构造函数
 75 {
 76    int i;
 77    memset(a,0,sizeof(a));
 78    for(i=0;i<len;i++)
 79    a[i]=T.a[i];
 80 }
 81 BigNum & BigNum::operator=(const BigNum &n) //重载赋值运算符，大数之间赋值运算
 82 {
 83    int i;
 84    len=n.len;
 85    memset(a,0,sizeof(a));
 86    for(i=0;i<len;i++)
 87    a[i]=n.a[i];
 88 return *this;
 89 }
 90 
 91 istream& operator>>(istream &in,BigNum &b)
 92 {
 93    char ch[MAXSIZE*4];
 94    int i=-1;
 95    in>>ch;
 96    int L=strlen(ch);
 97    int count=0,sum=0;
 98    for(i=L-1;i>=0;)
 99    {
100      sum=0;
101      int t=1;
102      for(int j=0;j<4&&i>=0;j++,i--,t*=10)
103      {
104       sum+=(ch[i]-'0')*t;
105       }
106       b.a[count]=sum;
107       count++;
108     }
109     b.len=count++;
110     return in;
111 }
112 
113 ostream& operator<<(ostream& out,BigNum& b) //重载输出运算符
114 {
115     int i;
116     cout<<b.a[b.len-1];
117     for(i=b.len-2;i>=0;i--)
118     {
119     printf("%04d",b.a[i]);
120     }
121     return out;
122 }
123 
124 BigNum BigNum::operator+(const BigNum &T)const //两个大数之间的相加运算
125 {
126     BigNum t(*this);
127     int i,big;
128     big=T.len>len?T.len:len;
129 for(i=0;i<big;i++)
130 {
131     t.a[i]+=T.a[i];
132     if(t.a[i]>MAXN)
133     {
134     t.a[i+1]++;
135     t.a[i]-=MAXN+1;
136 }
137 }
138 if(t.a[big]!=0)
139 t.len=big+1;
140 else t.len=big;
141 return t;
142 }
143 
144 BigNum BigNum::operator-(const BigNum &T)const //两个大数之间的相减运算
145 {
146    int i,j,big;
147     bool flag;
148     BigNum t1,t2;
149     if(*this>T)
150      {
151       t1=*this;
152       t2=T;
153       flag=0;
154       }
155     else
156     {
157       t1=T;
158       t2=*this;
159       flag=1;
160     }
161     big=t1.len;
162    for(i=0;i<big;i++)
163    {
164        if(t1.a[i]<t2.a[i])
165         {
166         j=i+1;
167         while(t1.a[j]==0)
168         j++;
169         t1.a[j--]--;
170         while(j>i)
171         t1.a[j--]+=MAXN;
172         t1.a[i]+=MAXN+1-t2.a[i];
173         }
174        else t1.a[i]-=t2.a[i];
175     }
176        t1.len=big;
177        while(t1.a[len-1]==0 && t1.len>1)
178        {
179          t1.len--;
180          big--;
181          }
182         if(flag)
183   t1.a[big-1]=0-t1.a[big-1];
184    return t1;
185  }
186 
187 BigNum BigNum::operator*(const BigNum &T)const //两个大数之间的相乘
188 {
189    BigNum ret;
190    int i,j,up;
191    int temp,temp1;
192    for(i=0;i<len;i++)
193    {
194    up=0;
195    for(j=0;j<T.len;j++)
196    {
197     temp=a[i]*T.a[j]+ret.a[i+j]+up;
198     if(temp>MAXN)
199     {
200     temp1=temp-temp/(MAXN+1)*(MAXN+1);
201     up=temp/(MAXN+1);
202     ret.a[i+j]=temp1;
203     }
204     else
205     {
206       up=0;
207       ret.a[i+j]=temp;
208     }
209    }
210     if(up!=0)
211     ret.a[i+j]=up;
212    }
213     ret.len=i+j;
214     while(ret.a[ret.len-1]==0 && ret.len>1)ret.len--;
215     return ret;
216 }
217 
218 BigNum BigNum::operator/(const int &b)const //大数对一个整数进行相除运算
219 {
220    BigNum ret;
221    int i,down=0;
222    for(i=len-1;i>=0;i--)
223    {
224     ret.a[i]=(a[i]+down*(MAXN+1))/b;
225     down=a[i]+down*(MAXN+1)-ret.a[i]*b;
226     }
227 
228     ret.len=len;
229     while(ret.a[ret.len-1]==0 && ret.len>1)
230     ret.len--;
231     return ret;
232 }
233 
234 int BigNum::operator%(const int &b)const //大数对一个 int类型的变量进行取模
235 {
236    int i,d=0;
237    for(i=len-1;i>=0;i--)
238    d=((d*(MAXN+1))%b+a[i])%b;
239    return d;
240 }
241 BigNum BigNum:: operator% (const BigNum &b) const
242 {
243     BigNum tmp=(*this);
244     while (tmp-b>0)
245     {
246      tmp=tmp-b;
247     }
248     if (!((tmp%b)>0)) tmp=tmp-b;
249     return tmp;
250 }
251 
252 BigNum BigNum::operator^(const int &n)const //大数的n次方运算
253 {
254    BigNum t,ret(1);
255    int i;
256    if(n<0)exit(-1);
257    if(n==0)return 1;
258    if(n==1)return *this;
259    int m=n;
260    while(m>1)
261    {
262      t=*this;
263      for(i=1;(i<<1)<=m;i<<=1)
264      t=t*t;
265      m-=i;
266      ret=ret*t;
267      if(m==1)ret=ret*(*this);
268      }
269   return ret;
270 }
271 
272 bool BigNum::operator>(const BigNum &T)const //大数和另一个大数的大小比较
273 {
274    int ln;
275    if(len>T.len)return true;
276    else if(len==T.len)
277    {
278         ln=len-1;
279         while(a[ln]==T.a[ln]&&ln>=0)
280         ln--;
281         if(ln>=0 && a[ln]>T.a[ln])
282           return true;
283         else
284         return false;
285    }
286         else
287         return false;
288 }
289 bool BigNum::operator>(const int &t)const //大数和一个int类型的变量的大小比较
290 {
291        BigNum b(t);
292        return *this>b;
293 }
294 void BigNum::print() //输出大数
295 {
296     int i;
297     printf("%d",a[len-1]);
298     for(i=len-2;i>=0;i--)
299     printf("%04d",a[i]);
300     printf("
");
301 }
302 BigNum f[1130];//卡特兰数
303 BigNum _Pow(BigNum &a,BigNum &b,BigNum &c)
304 {
305     BigNum d,e,f;
306     d=a,e=b,f=1;
307     while (e>0)
308     {
309         if (e%2) f=f*d%c;
310         e=e/2;
311         d=d*d%c;
312     }
313     return f;
314 }
315 
316 bool RabinMill(BigNum &n)
317 {
318     BigNum b,m,j,v,i;
319     m=n-1;
320     j=0;
321     while (m%2>0)
322     {
323         j=j+1;
324         m=m/2;
325     }
326 
327 }
328 int main()
329 {
330   /* f[0]=1;
331    for(int i=1;i<=435;i++)
332    f[i]=f[i-1]*(4*i-2)/(i+1);//卡特兰数递推式
333    int n;
334     while(scanf("%d",&n)==1)
335     {
336        if(n==-1)break;
337        f[n].print();
338     }
339     */
340     BigNum a,b,c;
341     cin>>a>>b;
342     c=a%b;
343     c.print();
344 
345     return 0;
346 }