[已解决]数据结构 大整数加法有待改正，请大家能够帮帮忙。

白砂糖

大整数加法运算
窗体底端
【问题描述】
给定测试数据若干组，每组有两个100位以内的正整数，要求程序给出这两个正整数相乘的结果。

【输入格式】
第一行为数据的组数 N，后面有N组测试数据，每组测试数据占一行，每行有两个100位以内的十进制整数。

【输出格式】

输出每一组测试数据的运算结果，每行一个结果。

【示例】
[输入]
6
47858628539074 212821064467
51357484452396 62369401380260
41972493335 769524402008059
16223931314069 936153278101
11775956124 981003321643
4648312830247 63220212506777
[输出]
10185324269616473782483558
3203135561691948572664102960
32298857834403116993786765
15188086483351158930902969
11552252073166227591732
293867324926193383538083919

我用的是vs2019

#include<iostream>
#include<string>
using namespace std;
const int MAX = 100;
class bigint
{
public:
        bigint() { length = 0; }
        bigint(int a[],int n);
        ~bigint() {};
        friend bigint addition(bigint a, bigint b);
        void Printlist();
private:
        int data[MAX];
        int length;
};
bigint::bigint(int a[],int n)
{
        length = n;
        if (length > MAX)throw"yichu";
        n--;
        for (int i = 0; i < length; i++)
                data[length - i] = a[i];


}
bigint addition(bigint A, bigint B)
{
        int flag = 0, i = 0;
        int n, m,len;

        bigint C;
        n = A.length;
        m = B.length;
        len = n > m ? n : m;
        for (i = 0; i < len; i++)
        {
                C.data[i] = A.data[i] + B.data[i];
                if (C.data[i] > 9)
                {
                        C.data[i] -= 10;
                        C.data[i + 1] += 1;
                }
        }
        if (C.data[len] != 0)
            len++;
        return C;
}
void bigint::Printlist()
{
        for (int i = length - 1; i >= 0; i--)
                cout << data[i] << endl;
}
int main()
{
        string a, b;
        int a1[MAX], b1[MAX];

        cout << "请输入1个大数：";
       
                cin >> a;
                cout << endl;
                cout << "请输入第二个大数：";
                cin >> b;
                int lena, lenb;
                lena = a.size();
                lenb = b.size();
                for (int i = 0; i < lena; i++)
                {
                        a1[i] = a[i] - '48';
                }
                for (int i = 0; i < lenb; i++)
                {
                        b1[i] = b[i] - '48';
                }
                bigint A(a1, lena), B(b1, lenb);
                bigint C;
                C = addition(A, B);

                cout << "结果：";
        C.Printlist();
        return 0;
}

最佳答案

月排行榜 / 总排行榜

xieglt

2020-12-28 10:34:57

fft算法，最快的乘法了，如果再不行，我也没办法。

1. 
   
2. #include <iostream>
   
3. #include <math.h>
   
4. #include <string>
   
5. 
   
6. #define        PI        (3.1415926535897932)
   
7. 
   
8. typedef struct tagComplex  
   
9. {
   
10.         double        X;
    
11.         double        Y;
    
12.        
    
13.         tagComplex()
    
14.         {
    
15.                 X = 0;
    
16.                 Y = 0;
    
17.         }
    
18.        
    
19.         tagComplex(const struct tagComplex & c)
    
20.         {
    
21.                 X = c.X;
    
22.                 Y = c.Y;
    
23.         }
    
24.        
    
25.         tagComplex(double x,double y = 0.0)
    
26.         {
    
27.                 X = x;
    
28.                 Y = y;
    
29.         }
    
30.        
    
31.         struct tagComplex & operator = (double x)
    
32.         {
    
33.                 X = x;
    
34.                 Y = 0;
    
35.                 return * this;
    
36.         }
    
37.        
    
38.        
    
39.         struct tagComplex & operator = (const tagComplex & c)
    
40.         {
    
41.                 X = c.X;
    
42.                 Y = c.Y;
    
43.                 return * this;
    
44.         }
    
45.        
    
46.         struct tagComplex & operator += (const tagComplex & c)
    
47.         {
    
48.                 X += c.X;
    
49.                 Y += c.Y;
    
50.                 return * this;
    
51.         }
    
52.        
    
53.         struct tagComplex & operator -= (const tagComplex & c)
    
54.         {
    
55.                 X -= c.X;
    
56.                 Y -= c.Y;
    
57.                 return * this;
    
58.         }
    
59.        
    
60.         struct tagComplex & operator *= (const tagComplex & c)
    
61.         {
    
62.                 COMPLEX t = * this;
    
63.                 X = t.X * c.X - t.Y * c.Y;
    
64.                 Y = t.X * c.Y + t.Y * c.X;
    
65.                 return * this;
    
66.         }
    
67.        
    
68.         struct tagComplex & operator /= (double n)
    
69.         {
    
70.                 X /= n;
    
71.                 Y /= n;
    
72.                 return * this;
    
73.         }
    
74.        
    
75.         void Mul(const tagComplex & a,const tagComplex & b)
    
76.         {
    
77.                 * this = a;
    
78.                 * this *= b;
    
79.         }
    
80.        
    
81.         operator double()
    
82.         {
    
83.                 return sqrt(X*X + Y*Y);
    
84.         }
    
85.        
    
86.         operator long()
    
87.         {
    
88.                 return (long)(X + 0.4);
    
89.         }
    
90.        
    
91.        
    
92. }COMPLEX, *LPCOMPLEX;
    
93. 
    
94. class CFFT  
    
95. {
    
96. private:
    
97.         CFFT(const CFFT &);
    
98.         CFFT & operator = (const CFFT &);
    
99.        
    
100. private:
     
101.         unsigned int BinaryRev(unsigned int ul,int len)
     
102.         {
     
103.                 unsigned int nRet = 0;
     
104.                
     
105.                 for(int i = 0 ; i < len ; i ++)
     
106.                 {
     
107.                         nRet <<= 1;
     
108.                         nRet |= (ul & 1);
     
109.                         ul >>= 1;
     
110.                 }
     
111.                
     
112.                 return nRet;
     
113.         }
     
114.        
     
115. public:
     
116.         CFFT(){};
     
117.         ~CFFT(){};
     
118.        
     
119.         void FFT(LPCOMPLEX fft,long n,bool flag = false)
     
120.         {
     
121.                 long i,j;
     
122.                 long log2n = (long)(log(n)/log(2) + 0.4);
     
123.                 COMPLEX omegaTemp;
     
124.                
     
125.                 for(i = 0 ; i < n ; i ++)
     
126.                 {
     
127.                         j = BinaryRev(i,log2n);
     
128.                        
     
129.                         if(i < j)
     
130.                         {
     
131.                                 omegaTemp = fft[i];
     
132.                                 fft[i] = fft[j];
     
133.                                 fft[j] = omegaTemp;
     
134.                         }
     
135.                 }
     
136.                
     
137.                 for(i = 1 ; i <= log2n ; i++)
     
138.                 {
     
139.                         long m = (1 << i);
     
140.                         COMPLEX omega_m(cos(2*PI/m),sin(2*PI/m));
     
141.                        
     
142.                         if(flag)
     
143.                         {
     
144.                                 omega_m.Y = -omega_m.Y;
     
145.                         }
     
146.                        
     
147.                         for(j = 0 ; j < n ; j += m)
     
148.                         {
     
149.                                 COMPLEX omegaBase(1,0);
     
150.                                
     
151.                                 for(long k = 0 ; k < m / 2 ; k ++)
     
152.                                 {
     
153.                                         long loc = j + k + m / 2;
     
154.                                        
     
155.                                         omegaTemp = omegaBase;
     
156.                                         omegaTemp *= fft[loc];
     
157.                                        
     
158.                                         fft[loc] = fft[j+k];
     
159.                                         fft[j+k] += omegaTemp;
     
160.                                         fft[loc] -= omegaTemp;
     
161.                                        
     
162.                                         omegaBase *= omega_m;
     
163.                                 }
     
164.                         }
     
165.                 }
     
166.                
     
167.                 if(flag)
     
168.                 {
     
169.                         for(i = 0 ; i < n ; i++)
     
170.                         {
     
171.                                 fft[i] /= n;
     
172.                         }
     
173.                 }
     
174.         }
     
175.        
     
176.         void Mul(std::string a,std::string b,std::string & out)
     
177.         {
     
178.                 long len = 1;
     
179.                 long i = a.length() > b.length() ? a.length() : b.length();
     
180.                 long j = 0;
     
181.                
     
182.                 while(i > len)
     
183.                 {
     
184.                         len <<= 1;
     
185.                 }
     
186.                
     
187.                 len <<= 1;
     
188.                
     
189.                 char * buffer = new char[(len * sizeof(COMPLEX) * 3)];
     
190.                 memset(buffer,0,(len * sizeof(COMPLEX) * 3));
     
191.                 LPCOMPLEX f1 = (LPCOMPLEX)buffer;
     
192.                 LPCOMPLEX f2 = f1 + len;
     
193.                 LPCOMPLEX f3 = f2 + len;
     
194.                
     
195.                
     
196.                
     
197.                 for(i = a.length()-1; i >= 0 ; i--)
     
198.                 {
     
199.                         f1[j++] = a[i] - 0X30;
     
200.                 }
     
201.                
     
202.                 for(j = 0, i = b.length()-1 ; i >= 0 ; i--)
     
203.                 {
     
204.                         f2[j++] = b[i] - 0X30;
     
205.                 }
     
206.                
     
207.                 FFT(f1,len);
     
208.                 FFT(f2,len);
     
209.                
     
210.                
     
211.                 for(i = 0 ; i < len ; i++)
     
212.                 {
     
213.                         f3[i].Mul(f1[i],f2[i]);
     
214.                 }
     
215.                
     
216.                 FFT(f3,len,true);
     
217.                
     
218.                 out = "";
     
219.                 typedef std::string::iterator SI;
     
220.                 SI si = out.begin();
     
221.                
     
222.                 long num = 0;
     
223.                
     
224.                 for(i = 0 ; i < len ; i ++)
     
225.                 {
     
226.                         long n = f3[i];
     
227.                         num += n;
     
228.                         out.insert(si,(num % 10 + 0X30));
     
229.                         num /= 10;               
     
230.                 }
     
231.                
     
232.                 while(out[0] == 0X30 && out.length() > 1)
     
233.                 {
     
234.                         out.erase(si);
     
235.                 }
     
236. 
     
237.                 delete [] buffer;
     
238.         }
     
239. };
     
240. 
     
241. 
     
242. int main()
     
243. {
     
244.         std::string a,b,c;   
     
245.     //输入两个大整数
     
246.     std::cin >> a >> b;
     
247.    
     
248.         CFFT fft;
     
249.         fft.Mul(a,b,c);
     
250.         std::cout << c;
     
251. 
     
252.     return 0;
     
253. }
     

复制代码

跳转到最佳答案楼层

xieglt

fft算法，最快的乘法了，如果再不行，我也没办法。

1. 
   
2. #include <iostream>
   
3. #include <math.h>
   
4. #include <string>
   
5. 
   
6. #define        PI        (3.1415926535897932)
   
7. 
   
8. typedef struct tagComplex  
   
9. {
   
10.         double        X;
    
11.         double        Y;
    
12.        
    
13.         tagComplex()
    
14.         {
    
15.                 X = 0;
    
16.                 Y = 0;
    
17.         }
    
18.        
    
19.         tagComplex(const struct tagComplex & c)
    
20.         {
    
21.                 X = c.X;
    
22.                 Y = c.Y;
    
23.         }
    
24.        
    
25.         tagComplex(double x,double y = 0.0)
    
26.         {
    
27.                 X = x;
    
28.                 Y = y;
    
29.         }
    
30.        
    
31.         struct tagComplex & operator = (double x)
    
32.         {
    
33.                 X = x;
    
34.                 Y = 0;
    
35.                 return * this;
    
36.         }
    
37.        
    
38.        
    
39.         struct tagComplex & operator = (const tagComplex & c)
    
40.         {
    
41.                 X = c.X;
    
42.                 Y = c.Y;
    
43.                 return * this;
    
44.         }
    
45.        
    
46.         struct tagComplex & operator += (const tagComplex & c)
    
47.         {
    
48.                 X += c.X;
    
49.                 Y += c.Y;
    
50.                 return * this;
    
51.         }
    
52.        
    
53.         struct tagComplex & operator -= (const tagComplex & c)
    
54.         {
    
55.                 X -= c.X;
    
56.                 Y -= c.Y;
    
57.                 return * this;
    
58.         }
    
59.        
    
60.         struct tagComplex & operator *= (const tagComplex & c)
    
61.         {
    
62.                 COMPLEX t = * this;
    
63.                 X = t.X * c.X - t.Y * c.Y;
    
64.                 Y = t.X * c.Y + t.Y * c.X;
    
65.                 return * this;
    
66.         }
    
67.        
    
68.         struct tagComplex & operator /= (double n)
    
69.         {
    
70.                 X /= n;
    
71.                 Y /= n;
    
72.                 return * this;
    
73.         }
    
74.        
    
75.         void Mul(const tagComplex & a,const tagComplex & b)
    
76.         {
    
77.                 * this = a;
    
78.                 * this *= b;
    
79.         }
    
80.        
    
81.         operator double()
    
82.         {
    
83.                 return sqrt(X*X + Y*Y);
    
84.         }
    
85.        
    
86.         operator long()
    
87.         {
    
88.                 return (long)(X + 0.4);
    
89.         }
    
90.        
    
91.        
    
92. }COMPLEX, *LPCOMPLEX;
    
93. 
    
94. class CFFT  
    
95. {
    
96. private:
    
97.         CFFT(const CFFT &);
    
98.         CFFT & operator = (const CFFT &);
    
99.        
    
100. private:
     
101.         unsigned int BinaryRev(unsigned int ul,int len)
     
102.         {
     
103.                 unsigned int nRet = 0;
     
104.                
     
105.                 for(int i = 0 ; i < len ; i ++)
     
106.                 {
     
107.                         nRet <<= 1;
     
108.                         nRet |= (ul & 1);
     
109.                         ul >>= 1;
     
110.                 }
     
111.                
     
112.                 return nRet;
     
113.         }
     
114.        
     
115. public:
     
116.         CFFT(){};
     
117.         ~CFFT(){};
     
118.        
     
119.         void FFT(LPCOMPLEX fft,long n,bool flag = false)
     
120.         {
     
121.                 long i,j;
     
122.                 long log2n = (long)(log(n)/log(2) + 0.4);
     
123.                 COMPLEX omegaTemp;
     
124.                
     
125.                 for(i = 0 ; i < n ; i ++)
     
126.                 {
     
127.                         j = BinaryRev(i,log2n);
     
128.                        
     
129.                         if(i < j)
     
130.                         {
     
131.                                 omegaTemp = fft[i];
     
132.                                 fft[i] = fft[j];
     
133.                                 fft[j] = omegaTemp;
     
134.                         }
     
135.                 }
     
136.                
     
137.                 for(i = 1 ; i <= log2n ; i++)
     
138.                 {
     
139.                         long m = (1 << i);
     
140.                         COMPLEX omega_m(cos(2*PI/m),sin(2*PI/m));
     
141.                        
     
142.                         if(flag)
     
143.                         {
     
144.                                 omega_m.Y = -omega_m.Y;
     
145.                         }
     
146.                        
     
147.                         for(j = 0 ; j < n ; j += m)
     
148.                         {
     
149.                                 COMPLEX omegaBase(1,0);
     
150.                                
     
151.                                 for(long k = 0 ; k < m / 2 ; k ++)
     
152.                                 {
     
153.                                         long loc = j + k + m / 2;
     
154.                                        
     
155.                                         omegaTemp = omegaBase;
     
156.                                         omegaTemp *= fft[loc];
     
157.                                        
     
158.                                         fft[loc] = fft[j+k];
     
159.                                         fft[j+k] += omegaTemp;
     
160.                                         fft[loc] -= omegaTemp;
     
161.                                        
     
162.                                         omegaBase *= omega_m;
     
163.                                 }
     
164.                         }
     
165.                 }
     
166.                
     
167.                 if(flag)
     
168.                 {
     
169.                         for(i = 0 ; i < n ; i++)
     
170.                         {
     
171.                                 fft[i] /= n;
     
172.                         }
     
173.                 }
     
174.         }
     
175.        
     
176.         void Mul(std::string a,std::string b,std::string & out)
     
177.         {
     
178.                 long len = 1;
     
179.                 long i = a.length() > b.length() ? a.length() : b.length();
     
180.                 long j = 0;
     
181.                
     
182.                 while(i > len)
     
183.                 {
     
184.                         len <<= 1;
     
185.                 }
     
186.                
     
187.                 len <<= 1;
     
188.                
     
189.                 char * buffer = new char[(len * sizeof(COMPLEX) * 3)];
     
190.                 memset(buffer,0,(len * sizeof(COMPLEX) * 3));
     
191.                 LPCOMPLEX f1 = (LPCOMPLEX)buffer;
     
192.                 LPCOMPLEX f2 = f1 + len;
     
193.                 LPCOMPLEX f3 = f2 + len;
     
194.                
     
195.                
     
196.                
     
197.                 for(i = a.length()-1; i >= 0 ; i--)
     
198.                 {
     
199.                         f1[j++] = a[i] - 0X30;
     
200.                 }
     
201.                
     
202.                 for(j = 0, i = b.length()-1 ; i >= 0 ; i--)
     
203.                 {
     
204.                         f2[j++] = b[i] - 0X30;
     
205.                 }
     
206.                
     
207.                 FFT(f1,len);
     
208.                 FFT(f2,len);
     
209.                
     
210.                
     
211.                 for(i = 0 ; i < len ; i++)
     
212.                 {
     
213.                         f3[i].Mul(f1[i],f2[i]);
     
214.                 }
     
215.                
     
216.                 FFT(f3,len,true);
     
217.                
     
218.                 out = "";
     
219.                 typedef std::string::iterator SI;
     
220.                 SI si = out.begin();
     
221.                
     
222.                 long num = 0;
     
223.                
     
224.                 for(i = 0 ; i < len ; i ++)
     
225.                 {
     
226.                         long n = f3[i];
     
227.                         num += n;
     
228.                         out.insert(si,(num % 10 + 0X30));
     
229.                         num /= 10;               
     
230.                 }
     
231.                
     
232.                 while(out[0] == 0X30 && out.length() > 1)
     
233.                 {
     
234.                         out.erase(si);
     
235.                 }
     
236. 
     
237.                 delete [] buffer;
     
238.         }
     
239. };
     
240. 
     
241. 
     
242. int main()
     
243. {
     
244.         std::string a,b,c;   
     
245.     //输入两个大整数
     
246.     std::cin >> a >> b;
     
247.    
     
248.         CFFT fft;
     
249.         fft.Mul(a,b,c);
     
250.         std::cout << c;
     
251. 
     
252.     return 0;
     
253. }
     

复制代码

xieglt

题目是求两数的积,不是和

1. #include <iostream>
   
2. #include <string.h>
   
3. 
   
4. #define        _BASE_SIZE        (1024)
   
5. 
   
6. class CBigInt
   
7. {
   
8. public:
   
9.         CBigInt()
   
10.         {
    
11.                 _num = new char[_BASE_SIZE];
    
12.                 memset(_num,0,_BASE_SIZE);
    
13.                 _size = _BASE_SIZE;
    
14.                 _len = 0;
    
15.         }
    
16. 
    
17.         CBigInt(const CBigInt & n)
    
18.         {
    
19.                 _num = new char[_BASE_SIZE];
    
20.                 memset(_num,0,_BASE_SIZE);
    
21.                 _size = _BASE_SIZE;
    
22.                 *this = n;               
    
23.         }
    
24. 
    
25.         ~CBigInt()
    
26.         {
    
27.                 if(_num != NULL)
    
28.                 {
    
29.                         delete [] _num;
    
30.                 }
    
31.         }
    
32. 
    
33.         CBigInt & operator = (const CBigInt & n)
    
34.         {
    
35.                 memcpy(_num,n._num,_size);
    
36.                 _len = n._len;
    
37.                 return * this;
    
38.         }
    
39. 
    
40.         friend CBigInt operator + (const CBigInt & a,const CBigInt b)
    
41.         {
    
42.                 CBigInt n = a;
    
43.                 n += b;
    
44.                 return n;
    
45.         }
    
46. 
    
47.         friend CBigInt operator * (const CBigInt & a,const CBigInt b)
    
48.         {
    
49.                 CBigInt n = a;
    
50.                 n *= b;
    
51.                 return n;
    
52.         }
    
53. 
    
54.         friend std::istream & operator >> (std::istream & in, CBigInt & n)
    
55.         {
    
56.                 char buffer[1024] = {0};
    
57. 
    
58.                 std::cin >> buffer;
    
59. 
    
60.                 int len = strlen(buffer);
    
61. 
    
62.                 for(int i=len-1,j=0 ; i>=0 ; i--)
    
63.                 {
    
64.                         n._num[j++] = buffer[i] - '0';
    
65.                 }
    
66. 
    
67.                 n._len = len;
    
68. 
    
69.                 return in;
    
70.         }
    
71. 
    
72.         friend std::ostream & operator << (std::ostream & out,const CBigInt & n)
    
73.         {
    
74.                 for(int i=n._len- 1 ; i>=0 ; i--)
    
75.                 {
    
76.                         char ch = (n._num[i] + '0');
    
77.                         std::cout << ch;
    
78.                 }
    
79. 
    
80.                 return out;
    
81.         }
    
82. private:
    
83.        
    
84.         CBigInt & operator += (const CBigInt & n)
    
85.         {
    
86.                 char value = 0;
    
87.                 char carry = 0;
    
88.                 int len = _len >= n._len ? _len : n._len;
    
89. 
    
90.                 for(int i=0 ; i<len ; i++)
    
91.                 {
    
92.                         value = carry;
    
93. 
    
94.                         if(i<_len)
    
95.                         {
    
96.                                 value += _num[i];
    
97.                         }
    
98. 
    
99.                         if(i<n._len)
    
100.                         {
     
101.                                 value += n._num[i];
     
102.                         }
     
103.                         carry = value / 10;
     
104.                         _num[i] = value % 10;
     
105.                 }
     
106. 
     
107.                 if(carry > 0 && i+1 < n._size)
     
108.                 {
     
109.                         _num[i++] =  carry;
     
110.                 }
     
111. 
     
112.                 _len = i;
     
113.                 return * this;
     
114.         }
     
115.        
     
116.         CBigInt & operator *= (char n)
     
117.         {
     
118.                 char value = 0;
     
119.                 char carry = 0;
     
120. 
     
121.                 for(int i=0 ; i<_len ; i++)
     
122.                 {
     
123.                         value = carry;
     
124.                         value += n * _num[i];
     
125.                         carry = value / 10;
     
126.                         _num[i] = value % 10;
     
127.                 }
     
128. 
     
129.                 if(carry > 0 && i+1 < _size)
     
130.                 {
     
131.                         _num[i++] = carry;
     
132.                 }
     
133. 
     
134.                 _len = i;
     
135.                
     
136.                 return * this;
     
137.         }
     
138. 
     
139.         CBigInt & operator *= (const CBigInt & n)
     
140.         {
     
141.                 CBigInt tempnum;
     
142.                 CBigInt addnum;
     
143. 
     
144.                 for(int i=0; i<n._len; i++)
     
145.                 {
     
146.                         tempnum = *this;
     
147.                         tempnum *= n._num[i];
     
148.                         tempnum <<= i;
     
149.                         addnum += tempnum;
     
150.                 }
     
151.                 *this = addnum;
     
152. 
     
153.                 return * this;
     
154.         }
     
155. 
     
156.         CBigInt & operator <<= (int i)
     
157.         {
     
158.                 if(i + _len + 1 < _size)
     
159.                 {
     
160.                         memcpy(_num+i,_num,_len);
     
161.                         memset(_num,0,i);
     
162.                         _len += i;
     
163.                 }
     
164. 
     
165.                 return * this;
     
166.         }
     
167. 
     
168. private:
     
169.         char * _num;
     
170.         int _size;
     
171.         int _len;
     
172. };
     
173. 
     
174. int main()
     
175. {
     
176.         CBigInt a,b;
     
177.        
     
178.         //输入两个大整数
     
179.         std::cin >> a >> b;
     
180.        
     
181.         //输出两数之和
     
182.         std::cout << a + b;
     
183.         //输出两数之积
     
184.         std::cout << a * b;
     
185. 
     
186.         return 0;
     
187. }
     

复制代码

白砂糖

请问，为什么提示i未定义呢？

xieglt

白砂糖 发表于 2020-12-29 08:45
请问，为什么提示i未定义呢？

c++支持变量即用即定义啊，你用的什么编译器？

xieglt

白砂糖 发表于 2020-12-29 08:45
请问，为什么提示i未定义呢？

实在不行，就把变量先定义吧

1. #include <iostream>
   
2. #include <string.h>
   
3. 
   
4. #define        _BASE_SIZE        (1024)
   
5. 
   
6. class CBigInt
   
7. {
   
8. public:
   
9.         CBigInt()
   
10.         {
    
11.                 _num = new char[_BASE_SIZE];
    
12.                 memset(_num,0,_BASE_SIZE);
    
13.                 _size = _BASE_SIZE;
    
14.                 _len = 0;
    
15.         }
    
16. 
    
17.         CBigInt(const CBigInt & n)
    
18.         {
    
19.                 _num = new char[_BASE_SIZE];
    
20.                 memset(_num,0,_BASE_SIZE);
    
21.                 _size = _BASE_SIZE;
    
22.                 *this = n;               
    
23.         }
    
24. 
    
25.         ~CBigInt()
    
26.         {
    
27.                 if(_num != NULL)
    
28.                 {
    
29.                         delete [] _num;
    
30.                 }
    
31.         }
    
32. 
    
33.         CBigInt & operator = (const CBigInt & n)
    
34.         {
    
35.                 memcpy(_num,n._num,_size);
    
36.                 _len = n._len;
    
37.                 return * this;
    
38.         }
    
39. 
    
40.         friend CBigInt operator + (const CBigInt & a,const CBigInt b)
    
41.         {
    
42.                 CBigInt n = a;
    
43.                 n += b;
    
44.                 return n;
    
45.         }
    
46. 
    
47.         friend CBigInt operator * (const CBigInt & a,const CBigInt b)
    
48.         {
    
49.                 CBigInt n = a;
    
50.                 n *= b;
    
51.                 return n;
    
52.         }
    
53. 
    
54.         friend std::istream & operator >> (std::istream & in, CBigInt & n)
    
55.         {
    
56.                 char buffer[1024] = {0};
    
57.                                 int i,j;
    
58.                                 int len;
    
59. 
    
60.                 std::cin >> buffer;
    
61. 
    
62.                 len = strlen(buffer);
    
63. 
    
64.                 for(i=len-1,j=0 ; i>=0 ; i--)
    
65.                 {
    
66.                         n._num[j++] = buffer[i] - '0';
    
67.                 }
    
68. 
    
69.                 n._len = len;
    
70. 
    
71.                 return in;
    
72.         }
    
73. 
    
74.         friend std::ostream & operator << (std::ostream & out,const CBigInt & n)
    
75.         {
    
76.                                 int i;
    
77.                                 char ch;
    
78. 
    
79.                 for(i=n._len- 1 ; i>=0 ; i--)
    
80.                 {
    
81.                         ch = (n._num[i] + '0');
    
82.                         std::cout << ch;
    
83.                 }
    
84. 
    
85.                 return out;
    
86.         }
    
87. private:
    
88.         
    
89.         CBigInt & operator += (const CBigInt & n)
    
90.         {               
    
91.                                 int i;
    
92.                 char value = 0;
    
93.                 char carry = 0;
    
94.                 int len = _len >= n._len ? _len : n._len;
    
95. 
    
96.                 for(i=0 ; i<len ; i++)
    
97.                 {
    
98.                         value = carry;
    
99. 
    
100.                         if(i<_len)
     
101.                         {
     
102.                                 value += _num[i];
     
103.                         }
     
104. 
     
105.                         if(i<n._len)
     
106.                         {
     
107.                                 value += n._num[i];
     
108.                         }
     
109.                         carry = value / 10;
     
110.                         _num[i] = value % 10;
     
111.                 }
     
112. 
     
113.                 if(carry > 0 && i+1 < n._size)
     
114.                 {
     
115.                         _num[i++] =  carry;
     
116.                 }
     
117. 
     
118.                 _len = i;
     
119.                 return * this;
     
120.         }
     
121.         
     
122.         CBigInt & operator *= (char n)
     
123.         {
     
124.                                 int i;
     
125.                 char value = 0;
     
126.                 char carry = 0;
     
127. 
     
128.                 for(i=0 ; i<_len ; i++)
     
129.                 {
     
130.                         value = carry;
     
131.                         value += n * _num[i];
     
132.                         carry = value / 10;
     
133.                         _num[i] = value % 10;
     
134.                 }
     
135. 
     
136.                 if(carry > 0 && i+1 < _size)
     
137.                 {
     
138.                         _num[i++] = carry;
     
139.                 }
     
140. 
     
141.                 _len = i;
     
142.                
     
143.                 return * this;
     
144.         }
     
145. 
     
146.         CBigInt & operator *= (const CBigInt & n)
     
147.         {
     
148.                 CBigInt tempnum;
     
149.                 CBigInt addnum;
     
150.                                 int i;
     
151. 
     
152.                 for(i=0; i<n._len; i++)
     
153.                 {
     
154.                         tempnum = *this;
     
155.                         tempnum *= n._num[i];
     
156.                         tempnum <<= i;
     
157.                         addnum += tempnum;
     
158.                 }
     
159.                 *this = addnum;
     
160. 
     
161.                 return * this;
     
162.         }
     
163. 
     
164.         CBigInt & operator <<= (int i)
     
165.         {
     
166.                 if(i + _len + 1 < _size)
     
167.                 {
     
168.                         memcpy(_num+i,_num,_len);
     
169.                         memset(_num,0,i);
     
170.                         _len += i;
     
171.                 }
     
172. 
     
173.                 return * this;
     
174.         }
     
175. 
     
176. private:
     
177.         char * _num;
     
178.         int _size;
     
179.         int _len;
     
180. };
     
181. 
     
182. int main()
     
183. {
     
184.         CBigInt a,b;
     
185.         
     
186.         //输入两个大整数
     
187.         std::cin >> a >> b;
     
188.         
     
189.         //输出两数之和
     
190.         std::cout << a + b;
     
191.         //输出两数之积
     
192.         std::cout << a * b;
     
193. 
     
194.         return 0;
     
195. }
     

复制代码

白砂糖

因为是在题库上提交，要求要在10000毫秒内完成，应该怎么办呢？

白砂糖

谢谢你，

白砂糖

我用的是vs2019，运行不出来

xieglt

白砂糖 发表于 2020-12-29 10:21
因为是在题库上提交，要求要在10000毫秒内完成，应该怎么办呢？

100位数的乘法，怎么也要不了10秒钟吧，你在什么平台上提交的？

qiaoqiaoqq

感谢大佬

白砂糖

数据结构课程设计在线平台