大数模板

  1 大数：
  2 #include <stdio.h>
  3 #include <string.h> 
  4 #include <stdlib.h> 
  5 #include <math.h>
  6 #include <assert.h>  
  7 #include <ctype.h> 
  8 #include <map>
  9 #include <string>
 10 #include <set>
 11 #include <bitset>
 12 #include <utility>
 13 #include <algorithm>
 14 #include <vector>
 15 #include <stack>
 16 #include <queue>
 17 #include <iostream>
 18 #include <fstream>
 19 #include <list>
 20 using  namespace  std;      
 21      
 22 const  int MAXL = 500;      
 23 struct  BigNum      
 24 {      
 25     int  num[MAXL];      
 26     int  len;      
 27 };      
 28      
 29 //高精度比较 a > b return 1, a == b return 0; a < b return -1;      
 30 int  Comp(BigNum &a, BigNum &b)      
 31 {      
 32     int  i;      
 33     if(a.len != b.len) return (a.len > b.len) ? 1 : -1;      
 34     for(i = a.len-1; i >= 0; i--)      
 35         if(a.num[i] != b.num[i]) return  (a.num[i] > b.num[i]) ? 1 : -1;      
 36     return  0;      
 37 }      
 38      
 39 //高精度加法      
 40 BigNum  Add(BigNum &a, BigNum &b)      
 41 {      
 42     BigNum c;      
 43     int  i, len;      
 44     len = (a.len > b.len) ? a.len : b.len;      
 45     memset(c.num, 0, sizeof(c.num));      
 46     for(i = 0; i < len; i++)      
 47     {      
 48         c.num[i] += (a.num[i]+b.num[i]);      
 49         if(c.num[i] >= 10)      
 50         {      
 51             c.num[i+1]++;      
 52             c.num[i] -= 10;      
 53         }      
 54     }      
 55     if(c.num[len])
 56         len++;      
 57     c.len = len;      
 58     return  c;      
 59 }      
 60 //高精度减法,保证a >= b      
 61 BigNum Sub(BigNum &a, BigNum &b)      
 62 {      
 63     BigNum  c;      
 64     int  i, len;      
 65     len = (a.len > b.len) ? a.len : b.len;      
 66     memset(c.num, 0, sizeof(c.num));      
 67     for(i = 0; i < len; i++)      
 68 {      
 69     If(i>=b.len)
 70         c.num[i]+=a.num[i];
 71     else
 72             c.num[i] += (a.num[i]-b.num[i]);      
 73         if(c.num[i] < 0)      
 74         {      
 75             c.num[i] += 10;      
 76             c.num[i+1]--;      
 77         }      
 78     }      
 79     while(c.num[len] == 0 && len > 1)
 80         len--;      
 81     c.len = len;      
 82     return  c;      
 83 }      
 84 //高精度乘以低精度，当b很大时可能会发生溢出int范围,具体情况具体分析      
 85 //如果b很大可以考虑把b看成高精度      
 86 BigNum Mul1(BigNum &a, int  &b)      
 87 {      
 88     BigNum c;      
 89     int  i, len;      
 90     len = a.len;      
 91     memset(c.num, 0, sizeof(c.num));      
 92     //乘以0，直接返回0      
 93     if(b == 0)       
 94     {      
 95         c.len = 1;      
 96         return  c;      
 97     }      
 98     for(i = 0; i < len; i++)      
 99     {      
100         c.num[i] += (a.num[i]*b);      
101         if(c.num[i] >= 10)      
102         {      
103             c.num[i+1] = c.num[i]/10;      
104             c.num[i] %= 10;      
105         }      
106     }      
107     while(c.num[len] > 0)      
108     {      
109         c.num[len+1] = c.num[len]/10;      
110         c.num[len++] %= 10;      
111     }      
112     c.len = len;       
113     return  c;      
114 }      
115      
116 //高精度乘以高精度,注意要及时进位，否则肯能会引起溢出,但这样会增加算法的复杂度，      
117 //如果确定不会发生溢出, 可以将里面的while改成if      
118 BigNum  Mul2(BigNum &a, BigNum &b)      
119 {      
120     int i, j, len = 0;      
121     BigNum  c;      
122     memset(c.num, 0, sizeof(c.num));      
123     for(i = 0; i < a.len; i++)
124     {
125         for(j = 0; j < b.len; j++)      
126         {      
127             c.num[i+j] += (a.num[i]*b.num[j]);      
128             if(c.num[i+j] >= 10)      
129             {      
130                 c.num[i+j+1] += c.num[i+j]/10;      
131                 c.num[i+j] %= 10;      
132             }      
133         }
134     }
135 len = a.len+b.len-1;
136     if(c.num[len])
137     len++;       
138     while(c.num[len-1] == 0 && len > 1)
139         len--;     
140     c.len = len;      
141     return  c;      
142 }      
143      
144 //高精度除以低精度,除的结果为c, 余数为f      
145 void Div1(BigNum &a, int &b, BigNum &c, int &f)      
146 {      
147     int  i, len = a.len;      
148     memset(c.num, 0, sizeof(c.num));      
149     f = 0;      
150     for(i = a.len-1; i >= 0; i--)      
151     {      
152         f = f*10+a.num[i];      
153         c.num[i] = f/b;      
154         f %= b;      
155     }      
156     while(len > 1 && c.num[len-1] == 0)
157         len--;      
158     c.len = len;      
159 }      
160 //高精度*10      
161 void  Mul10(BigNum &a)      
162 {      
163     int  i, len = a.len;      
164     for(i = len; i >= 1; i--)      
165         a.num[i] = a.num[i-1];      
166     a.num[i] = 0;      
167     len++;      
168     //if a == 0      
169     while(len > 1 && a.num[len-1] == 0)
170         len--;  
171     a.len=len;    
172 }      
173      
174 //高精度除以高精度，除的结果为c，余数为f      
175 void Div2(BigNum &a, BigNum &b, BigNum &c, BigNum &f)      
176 {      
177     int  i, len = a.len;      
178     memset(c.num, 0, sizeof(c.num));      
179     memset(f.num, 0, sizeof(f.num));      
180     f.len = 1;      
181     for(i = len-1;i >= 0;i--)      
182     {      
183         Mul10(f);      
184         //余数每次乘10      
185         f.num[0] = a.num[i];      
186         //然后余数加上下一位      
187         ///利用减法替换除法      
188         while(Comp(f, b) >= 0)      
189         {
190             f = Sub(f, b);      
191             c.num[i]++;      
192         }      
193     }      
194     while(len > 1 && c.num[len-1] == 0)
195         len--;      
196     c.len = len;      
197 }   
198 void  print(BigNum &a)   //输出大数   
199 {      
200     int  i;      
201     for(i = a.len-1; i >= 0; i--)      
202         printf("%d", a.num[i]);      
203     puts("");      
204 }      
205 //将字符串转为大数存在BigNum结构体里面      
206 BigNum ToNum(char *s)      
207 {      
208     int i, j;      
209     BigNum  a;      
210     a.len = strlen(s);      
211     for(i = 0, j = a.len-1; s[i] != ''; i++, j--)      
212         a.num[i] = s[j]-'0';      
213     return  a;      
214 }      
215      
216 void Init(BigNum &a, char *s, int &tag)   //将字符串转化为大数
217 {   
218     int  i = 0, j = strlen(s); 
219     if(s[0] == '-')
220     {
221         j--;
222         i++;
223         tag *= -1;
224     }
225     a.len = j;
226     for(; s[i] != ''; i++, j--)
227         a.num[j-1] = s[i]-'0';
228 }   
229   
230 int main(void)      
231 {      
232     BigNum a, b;   
233     char  s1[100], s2[100];   
234     while(scanf("%s %s", s1, s2) != EOF)   
235     {   
236         int tag = 1;   
237         Init(a, s1, tag);    //将字符串转化为大数
238         Init(b, s2, tag);   
239         a = Mul2(a, b);   
240         if(a.len == 1 && a.num[0] == 0)   
241         {   
242             puts("0");   
243         }   
244         else    
245         {   
246             if(tag < 0) putchar('-');   
247             print(a);   
248         }   
249     }   
250     return 0;   
251 }