高精度模板

http://acm.xidian.edu.cn/problem.php?id=1046

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 struct bign{
  4     int num[1000];
  5     int len,symbol;
  6 };
  7 bign a,b;
  8 
  9 bool init(bign &a){
 10     memset(&a,0,sizeof a);
 11     string s;
 12     if(!(cin>>s)) return false;
 13     a.len=s.length();
 14     for(int i=0;i<a.len;i++){
 15         a.num[i]=s[a.len-i-1]-'0';
 16     }
 17     return true;
 18 }
 19 
 20 int compare(bign &a,bign &b){
 21     if(a.len>b.len) return 1;
 22     if(a.len<b.len) return -1;
 23     for(int i=a.len-1;i>=0;i--){
 24         if(a.num[i]>b.num[i]) return 1;
 25         if(a.num[i]<b.num[i]) return -1;
 26     }
 27     return 0;
 28 }
 29 
 30 void print(bign &a){
 31     if(a.len==0){
 32         printf("0");
 33         return;
 34     }
 35     if(a.symbol==-1) printf("-");
 36     for(int i=a.len-1;i>=0;i--){
 37         printf("%d",a.num[i]);
 38     };
 39     return;
 40 }
 41 
 42 bign add(bign &a,bign &b){
 43     bign c={0};
 44     c.len=a.len>b.len?a.len:b.len;
 45     for(int i=0;i<c.len;i++){
 46         c.num[i]+=a.num[i]+b.num[i];
 47         if(c.num[i]>=10){
 48             c.num[i+1]+=c.num[i]/10;
 49             c.num[i]%=10;
 50         }
 51     }
 52     if(c.num[c.len]>0) c.len++;
 53     return c;
 54 }
 55 
 56 bign sub(bign a,bign b){
 57     int flag=compare(a,b);
 58     if(flag==0){
 59         a.len=0;
 60         return a;
 61     }    
 62     if(flag==-1){
 63         swap(a,b);
 64         a.symbol=-1;
 65     }
 66     
 67     for(int i=0;i<a.len;i++){
 68         if(a.num[i]<b.num[i]){
 69             a.num[i+1]--;
 70             a.num[i]+=10;
 71         }
 72         a.num[i]-=b.num[i];
 73     }
 74     while(a.num[a.len-1]==0) a.len--;
 75     return a;
 76 }
 77 
 78 bign mul(bign &a,bign &b){
 79     bign c={0};
 80     for(int i=0;i<a.len;i++){
 81         for(int j=0;j<b.len;j++){
 82             c.num[i+j]+=a.num[i]*b.num[j];
 83             if(c.num[i+j]>=10){
 84                 c.num[i+j+1]+=c.num[i+j]/10;
 85                 c.num[i+j]%=10;
 86             }
 87         }
 88     }
 89     c.len=a.len+b.len;
 90     while(c.len>1&&c.num[c.len-1]==0) c.len--;
 91     return c;
 92 }
 93 
 94 void mul10(bign &a){
 95     int i;
 96     for(i=a.len-1;i>=0;i--){
 97          a.num[i+1]=a.num[i];
 98     }
 99      a.num[i]=0;
100      a.len++;
101      while(a.len>1&&a.num[a.len-1]==0) a.len--;
102  }
103  
104 void div(bign &a, bign &b,bign &c,bign &f){
105     f.len = 1;
106     c.len=a.len;
107     for(int i=a.len-1;i>=0;i--){
108         mul10(f);
109         f.num[0] = a.num[i];
110         while(compare(f,b)>=0){
111             f=sub(f, b);
112             c.num[i]++;
113          }
114      }
115     while(c.len>1&&c.num[c.len-1]==0) c.len--;
116  }
117  
118 
119 
120 int main(){
121     while(init(a)&&init(b)){
122     bign g={0},f={0};
123     g.len=1;
124     bign c=add(a,b),d=sub(a,b),e=mul(a,b);
125     div(a,b,g,f);
126     print(c);printf(" ");
127     print(d);printf(" ");
128     print(e);printf(" ");
129     print(g);printf(" ");
130     print(f);
131     printf("
");
132 }
133     return 0;
134 }

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