UVA_Product

Description

Product

The Problem

The problem is to multiply two integers X, Y. (0<=X,Y<10²⁵⁰)

The Input

The input will consist of a set of pairs of lines. Each line in pair contains one multiplyer.

The Output

For each input pair of lines the output line should consist one integer the product.

Sample Input

12
12
2
222222222222222222222222

Sample Output

144
444444444444444444444444

题意：简单的2个大数的乘积；

套用刘汝佳的大数相乘模板；

要注意的是数组的大小；这里0<=X,Y<10^{250 ；}

所以数组至少要开到500以上；

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #define UNIT 10
  6 
  7 using namespace std;
  8 
  9 struct Bignum
 10 {
 11     int val[550];
 12     int len;
 13 
 14     Bignum ()
 15     {
 16         memset (val, 0, sizeof(val));
 17         len = 1;
 18     }
 19 
 20     Bignum operator = (const int &a)
 21     {
 22         int t, p = a;
 23         len = 0;
 24         while (p >= UNIT)
 25         {
 26             t = p - (p/UNIT)*UNIT;
 27             p = p / UNIT;
 28             val[len++] = t;
 29         }
 30         val[len++] = p;
 31         return *this;
 32     }
 33 
 34     Bignum operator + (const Bignum &a) const//大数加大数
 35     {
 36         Bignum x = a;
 37         int L;
 38         L = a.len > len ? a.len : len;
 39         for (int i = 0; i < L; ++i)
 40         {
 41             x.val[i] += val[i];
 42             if (x.val[i] >= UNIT)
 43             {
 44                 x.val[i+1]++;
 45                 x.val[i] -= UNIT;
 46             }
 47         }
 48         if (x.val[L] != 0)
 49             x.len = L+1;
 50         else
 51             x.len = L;
 52         return x;
 53     }
 54 
 55     Bignum operator - (const Bignum &a) const
 56     {
 57         bool flag;
 58         Bignum x1, x2;
 59         if (*this > a)
 60         {
 61             x1 = *this;
 62             x2 = a;
 63             flag = 0;
 64         }
 65         else
 66         {
 67             x1 = a;
 68             x2 = *this;
 69             flag = 1;
 70         }
 71         int j, L = x1.len;
 72         for (int i = 0; i < L; ++i)
 73         {
 74             if (x1.val[i] < x2.val[i])
 75             {
 76                 j = i+1;
 77                 while (x1.val[j] == 0)
 78                     j++;
 79                 x1.val[j--]--;
 80                 while (j > i)
 81                     x1.val[j--] += UNIT-1;
 82                 x1.val[i] += UNIT-x2.val[i];
 83             }
 84             else
 85                 x1.val[i] -= x2.val[i];
 86         }
 87         while (x1.val[x1.len-1] == 0 && x1.len > 1)
 88             x1.len--;
 89         if (flag)
 90             x1.val[x1.len-1] = -x1.val[x1.len-1];
 91         return x1;
 92     }
 93 
 94     Bignum operator * (const Bignum &a) const//大数乘大数
 95     {
 96         Bignum x;
 97         int i, j, up;
 98         int x1, x2;
 99         for (i = 0; i < len; i++)
100         {
101             up = 0;
102             for (j = 0; j < a.len; j++)
103             {
104                 x1 = val[i]*a.val[j] + x.val[i+j] + up;
105                 if (x1 >= UNIT)
106                 {
107                     x2 = x1 - x1/UNIT*UNIT;
108                     up = x1 / UNIT;
109                     x.val[i+j] = x2;
110                 }
111                 else
112                 {
113                     up = 0;
114                     x.val[i+j] = x1;
115                 }
116             }
117             if (up != 0)
118                 x.val[i+j] = up;
119         }
120         x.len = i + j;
121         while (x.val[x.len-1] == 0 && x.len > 1)
122             x.len--;
123         return x;
124     }
125 
126     Bignum operator / (const int &a) const//大数除小数
127     {
128         Bignum x;
129         int down = 0;
130         for (int i = len-1; i >= 0; --i)
131         {
132             x.val[i] = (val[i]+down*UNIT) / a;
133             down = val[i] + down*UNIT - x.val[i]*a;
134         }
135         x.len = len;
136         while (x.val[x.len-1] == 0 && x.len > 1)
137             x.len--;
138         return x;
139     }
140 
141     int operator % (const int &a) const//大数模小数
142     {
143         int x = 0;
144         for (int i = len-1; i >= 0; --i)
145             x = ((x*UNIT)%a+val[i]) % a;
146         return x;
147     }
148 
149     Bignum operator ^ (const int &a) const
150     {
151         Bignum p, x;
152         x.val[0] = 1;
153         if(a < 0)
154             exit(-1);
155         if(a == 0)
156             return x;
157         if(a == 1)
158             return *this;
159         int n = a, i;
160         while(n > 1)
161         {
162             p = *this;
163             for(i = 1; (i<<1) <= n; i<<=1)
164                 p = p * p;
165             n -= i;
166             x = x * p;
167             if(n == 1)
168                 x = x * (*this);
169         }
170         return x;
171     }
172 
173     bool operator > (const Bignum &a) const
174     {
175         int now;
176         if (len > a.len)
177             return true;
178         else if (len == a.len)
179         {
180             now = len - 1;
181             while (val[now] == a.val[now] && now >= 0)
182                 now--;
183             if(now >= 0 && val[now] > a.val[now])
184                 return true;
185             else
186                 return false;
187         }
188         else
189             return false;
190     }
191 };
192 
193 
194 char a[555],b[555];
195 int main()
196 {
197    // freopen("ACM.txt","r",stdin);
198 
199     while(cin>>a>>b)
200     {
201         Bignum x1,x2,ans;
202         int La=strlen(a);
203         int Lb=strlen(b);
204         x1.len=0;
205         x2.len=0;
206         for(int i=La-1;i>=0;i--)
207         x1.val[x1.len++]=a[i]-'0';
208         for(int i=Lb-1;i>=0;i--)
209         x2.val[x2.len++]=b[i]-'0';
210         ans=x1*x2;
211         for(int i=ans.len-1;i>=0;i--)
212         cout<<ans.val[i];
213         cout<<endl;
214     }
215     return 0;
216 }

View Code