大数处理详解模版

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<math.h>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<vector>
  8 #include<set>
  9 #include<stack>
 10 #include<string>
 11 #include<sstream>
 12 #include<map>
 13 #include<cctype>
 14 #include<limits.h>
 15 using namespace std;
 16 char str[1000001],modd[1000000];   // 这里做了修改 多加了两个0 能储存更大的值 
 17 #define MAXN 9999           //
 18 #define MAXSIZE 10              // 只和 下面的 重载运算符 有关 .
 19 #define DLEN 4         //  决定了 , 下面的 int 型 a 数组 ,  一个 单位内 储存 数字为 几位 ( 当然是 空间利用的 越充分 越好 , 不过 这要根据实际情况来说 . )
 20 class BigNum
 21 {
 22 private:
 23     int a[100010];    //可以控制大数的位数
 24     int len;       //大数长度
 25 public:
 26     BigNum(){ len = 1;memset(a,0,sizeof(a)); }   //构造函数
 27     BigNum(const int);       //将一个int类型的变量转化为大数
 28     BigNum(const char*);     //将一个字符串类型的变量转化为大数
 29     BigNum(const BigNum &);  //拷贝构造函数
 30     BigNum &operator=(const BigNum &);   //重载赋值运算符，大数之间进行赋值运算
 31 
 32     friend istream& operator>>(istream&,  BigNum&);   //重载输入运算符
 33     friend ostream& operator<<(ostream&,  BigNum&);   //重载输出运算符
 34 
 35     BigNum operator+(const BigNum &) const;   //重载加法运算符，两个大数之间的相加运算
 36     BigNum operator-(const BigNum &) const;   //重载减法运算符，两个大数之间的相减运算
 37     BigNum operator*(const BigNum &) const;   //重载乘法运算符，两个大数之间的相乘运算
 38     BigNum operator/(const int   &) const;    //重载除法运算符，大数对一个整数进行相除运算
 39 
 40     BigNum operator^(const int  &) const;    //大数的n次方运算
 41     int    operator%(const int  &) const;    //大数对一个int类型的变量进行取模运算
 42     bool   operator>(const BigNum & T)const;   //大数和另一个大数的大小比较
 43     bool   operator>(const int & t)const;      //大数和一个int类型的变量的大小比较
 44 
 45     void print();       //输出大数
 46 };
 47 BigNum::BigNum(const int b)     //将一个int类型的变量转化为大数
 48 {
 49     int c,d = b;
 50     len = 0;
 51     memset(a,0,sizeof(a));
 52     while(d > MAXN)
 53     {
 54         c = d - (d / (MAXN + 1)) * (MAXN + 1);
 55         d = d / (MAXN + 1);
 56         a[len++] = c;
 57     }
 58     a[len++] = d;
 59 }
 60 BigNum::BigNum(const char*s)     //将一个字符串类型的变量转化为大数
 61 {
 62     int t,k,index,l,i;
 63     memset(a,0,sizeof(a));
 64     l=strlen(s);
 65     len=l/DLEN;
 66     if(l%DLEN)
 67         len++;
 68     index=0;
 69     for(i=l-1;i>=0;i-=DLEN)
 70     {
 71         t=0;
 72         k=i-DLEN+1;
 73         if(k<0)
 74             k=0;
 75         for(int j=k;j<=i;j++)
 76             t=t*10+s[j]-'0';
 77         a[index++]=t;
 78     }
 79 }
 80 BigNum::BigNum(const BigNum & T) : len(T.len)  //拷贝构造函数
 81 {
 82     int i;
 83     memset(a,0,sizeof(a));
 84     for(i = 0 ; i < len ; i++)
 85         a[i] = T.a[i];
 86 }
 87 BigNum & BigNum::operator=(const BigNum & n)   //重载赋值运算符，大数之间进行赋值运算
 88 {
 89     int i;
 90     len = n.len;
 91     memset(a,0,sizeof(a));
 92     for(i = 0 ; i < len ; i++)
 93         a[i] = n.a[i];
 94     return *this;
 95 }
 96 istream& operator>>(istream & in,  BigNum & b)   //重载输入运算符
 97 {
 98     char ch[MAXSIZE*4];
 99     int i = -1;
100     in>>ch;
101     int l=strlen(ch);
102     int count=0,sum=0;
103     for(i=l-1;i>=0;)
104     {
105         sum = 0;
106         int t=1;
107         for(int j=0;j<4&&i>=0;j++,i--,t*=10)
108         {
109             sum+=(ch[i]-'0')*t;
110         }
111         b.a[count]=sum;
112         count++;
113     }
114     b.len =count++;
115     return in;
116 
117 }
118 ostream& operator<<(ostream& out,  BigNum& b)   //重载输出运算符
119 {
120     int i;
121     cout << b.a[b.len - 1];
122     for(i = b.len - 2 ; i >= 0 ; i--)
123     {
124         cout.width(DLEN);
125         cout.fill('0');
126         cout << b.a[i];
127     }
128     return out;
129 }
130 
131 BigNum BigNum::operator+(const BigNum & T) const   //两个大数之间的相加运算
132 {
133     BigNum t(*this);
134     int i,big;      //位数
135     big = T.len > len ? T.len : len;
136     for(i = 0 ; i < big ; i++)
137     {
138         t.a[i] +=T.a[i];
139         if(t.a[i] > MAXN)
140         {
141             t.a[i + 1]++;
142             t.a[i] -=MAXN+1;
143         }
144     }
145     if(t.a[big] != 0)
146         t.len = big + 1;
147     else
148         t.len = big;
149     return t;
150 }
151 BigNum BigNum::operator-(const BigNum & T) const   //两个大数之间的相减运算
152 {
153     int i,j,big;
154     bool flag;
155     BigNum t1,t2;
156     if(*this>T)
157     {
158         t1=*this;
159         t2=T;
160         flag=0;
161     }
162     else
163     {
164         t1=T;
165         t2=*this;
166         flag=1;
167     }
168     big=t1.len;
169     for(i = 0 ; i < big ; i++)
170     {
171         if(t1.a[i] < t2.a[i])
172         {
173             j = i + 1;
174             while(t1.a[j] == 0)
175                 j++;
176             t1.a[j--]--;
177             while(j > i)
178                 t1.a[j--] += MAXN;
179             t1.a[i] += MAXN + 1 - t2.a[i];
180         }
181         else
182             t1.a[i] -= t2.a[i];
183     }
184     t1.len = big;
185     while(t1.a[len - 1] == 0 && t1.len > 1)
186     {
187         t1.len--;
188         big--;
189     }
190     if(flag)
191         t1.a[big-1]=0-t1.a[big-1];
192     return t1;
193 }
194 
195 BigNum BigNum::operator*(const BigNum & T) const   //两个大数之间的相乘运算
196 {
197     BigNum ret;
198     int i,j,up;
199     int temp,temp1;
200     for(i = 0 ; i < len ; i++)
201     {
202         up = 0;
203         for(j = 0 ; j < T.len ; j++)
204         {
205             temp = a[i] * T.a[j] + ret.a[i + j] + up;
206             if(temp > MAXN)
207             {
208                 temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
209                 up = temp / (MAXN + 1);
210                 ret.a[i + j] = temp1;
211             }
212             else
213             {
214                 up = 0;
215                 ret.a[i + j] = temp;
216             }
217         }
218         if(up != 0)
219             ret.a[i + j] = up;
220     }
221     ret.len = i + j;
222     while(ret.a[ret.len - 1] == 0 && ret.len > 1)
223         ret.len--;
224     return ret;
225 }
226 BigNum BigNum::operator/(const int & b) const   //大数对一个整数进行相除运算
227 {
228     BigNum ret;
229     int i,down = 0;
230     for(i = len - 1 ; i >= 0 ; i--)
231     {
232         ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
233         down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
234     }
235     ret.len = len;
236     while(ret.a[ret.len - 1] == 0 && ret.len > 1)
237         ret.len--;
238     return ret;
239 }
240 int BigNum::operator %(const int & b) const    //大数对一个int类型的变量进行取模运算
241 {
242     int i,d=0;
243     for (i = len-1; i>=0; i--)
244     {
245         d = ((d * (MAXN+1))% b + a[i])% b;     // 大数  对 int 整形变量取模运算 的时候 得到值 也就是 在int 范围之内  .
246     }
247     return d;                           //  这时候 直接  输出就行 .
248 }
249 BigNum BigNum::operator^(const int & n) const    //大数的n次方运算
250 {
251     BigNum t,ret(1);
252     int i;
253     if(n<0)
254         exit(-1);
255     if(n==0)
256         return 1;
257     if(n==1)
258         return *this;
259     int m=n;
260     while(m>1)
261     {
262         t=*this;
263         for( i=1;i<<1<=m;i<<=1)
264         {
265             t=t*t;
266         }
267         m-=i;
268         ret=ret*t;
269         if(m==1)
270             ret=ret*(*this);
271     }
272     return ret;
273 }
274 bool BigNum::operator>(const BigNum & T) const   //大数和另一个大数的大小比较
275 {
276     int ln;
277     if(len > T.len)
278         return true;
279     else if(len == T.len)
280     {
281         ln = len - 1;
282         while(a[ln] == T.a[ln] && ln >= 0)
283             ln--;
284         if(ln >= 0 && a[ln] > T.a[ln])
285             return true;
286         else
287             return false;
288     }
289     else
290         return false;
291 }
292 bool BigNum::operator >(const int & t) const    //大数和一个int类型的变量的大小比较
293 {
294     BigNum b(t);
295     return *this>b;
296 }
297 
298 void BigNum::print()    //输出大数
299 {
300     int i;
301     cout << a[len - 1];
302     for(i = len - 2 ; i >= 0 ; i--)
303     {
304         cout.width(DLEN);
305         cout.fill('0');
306         cout << a[i];
307     }
308     cout << endl;
309 }
310 int main()
311 {
312     int n;
313     while(scanf("%d",&n)!=EOF)
314     {
315         BigNum big(str);
316         big=1;
317         for(int i=1;i<=n;i++)
318         {
319             big=big*i;
320         }
321         big.print();
322     }
323 }
大数处理 详解 模版

大数处理详解模版
