大数（模板）

参考：

(48条消息) 大数(加、减、乘、除、低精度*大数)模板详解（C++）_氵青-风的博客-CSDN博客_c++ 大数

模板：

  1 //大数加，减，乘，除，阶乘（低精度*大数）
  2 //大数
  3 #include<bits/stdc++.h>
  4 #include<cstring>
  5 using namespace std;
  6 //初始化，补全位数 
  7 void inital(string &a,string &b)
  8 {
  9     while(a.size()<b.size()) a='0'+a;
 10     while(b.size()<a.size()) b='0'+b;
 11 }
 12 //找最大值，使a>b 
 13 void findmax(string &a,string &b)
 14 {
 15     string cmp;
 16     if(a<b)
 17     {
 18         cmp=a;
 19         a=b;
 20         b=cmp;
 21     }
 22 }
 23 //删除第一个'0' 
 24 bool del(string &a)
 25 {
 26     if(a[0]=='0')
 27     {
 28     a.erase(0,1);
 29     return true;
 30     }
 31     else
 32     return false;
 33 }
 34 //删除全部的'0',基于del 
 35 void delall(string &a)
 36 {
 37     while(del(a))
 38     {
 39         del(a);
 40     }
 41 }
 42 //大数加法 
 43 string bigadd(string a,string b)
 44 {
 45     inital(a,b);//初始化，先补位，使a，b对齐 
 46     //a，b前都加一个'0'方便进位（例如三位数加三位数最多为四位数） 
 47     a='0'+a;
 48     b='0'+b;
 49     //从后往前，按位加 
 50     for(int i=a.size()-1;i>=0;i--)
 51     {
 52         //减'0'的ASCII码，得到准确数据 
 53         int num1=a[i]-'0';
 54         int num2=b[i]-'0';
 55         //如果相加大于10，进位 
 56         if(num1+num2>9)
 57         { 
 58             a[i-1]=a[i-1]-'0'+1+'0';
 59             a[i]=num1+num2-10+'0';
 60         }
 61         else
 62         {
 63             a[i]=num1+num2+'0';
 64         }
 65     }
 66     //删除最前面的'0' 
 67     del(a);
 68     //cout<<a<<endl;
 69     return a;
 70 }
 71 //大数减法，基本与大数加法相同 
 72 string bigsub(string a,string b)
 73 {
 74     inital(a,b);
 75     //找到a，b中的最大值，来分别充当减数与被减数 
 76     findmax(a,b);
 77     for(int i=a.size()-1;i>=0;i--)
 78     {
 79         int num1=a[i]-'0';
 80         int num2=b[i]-'0';
 81         //被减数小于减少，进行借位 
 82         if(num1<num2)
 83         {
 84             a[i-1]=a[i-1]-'0'-1+'0';
 85             a[i]=(num1+10-num2)+'0';
 86         }
 87         else
 88         {
 89             a[i]=num1-num2+'0';
 90         }
 91     }
 92     //删除a前面全部的'0' 
 93     delall(a);
 94     cout<<a<<endl;
 95     return a;
 96  } 
 97  //大数乘法，基于大数加法 
 98 void bigmul(string a,string b)
 99 {
100     //先考虑特殊情况 
101     //删除a，b前面所有的零，若其中一个为空，表示其中一个乘数为0，那么a*b=0 
102     delall(a);
103     delall(b);
104     if(a==""||b=="")
105     {
106         cout<<"0"<<endl;
107         return;
108     }
109     //考虑完特殊情况后初始化a，b 
110     inital(a,b);
111     //找到a，b中的最大值，把问题转化为大数加分 
112     findmax(a,b);
113     string res="0";//存储答案 
114     delall(b);//删除b前所有的'0'，把b拆分充当小数 
115     for(int i=b.size()-1;i>=0;i--)
116     {
117         int num1=b[i]-'0';
118         //例如：10*5555=1*55550 
119         if(i!=b.size()-1)
120         {
121             a=a+'0';
122         }
123         //例如5*10转化为:5个10相加 
124         for(int j=1;j<=num1;j++)
125         {
126             res=bigadd(res,a);
127         }
128     }
129     //删除res前所有的'0' 
130     delall(res);
131     cout<<res<<endl;
132 }
133 //大数除法，注意每次判断前都要补全 
134 //相当于求：被除数是除数的几倍 
135 void bigdiv(string a,string b)
136 {
137     inital(a,b);//将要判断a与b的大小关系，需补全 
138     //特殊情况 
139     if(a<b)
140     {
141         cout<<"0"<<endl;
142         return;
143     }
144     delall(b);
145     string res="0";//存储答案 
146     string tmp=b;//存储每次的除数=b*restmp 
147     string restmp="1";//倍数 
148     for(int i=1;i<=(a.size()-b.size());i++)
149     {
150         //计算a与b相差的位数，即为相差的倍数 
151         tmp+='0';
152         restmp+='0';
153     }
154     inital(a,b);//将要进行判断a，b的大小关系，需补全 
155     while(a>=b)
156     {
157         inital(a,tmp);//将要判断a，tmp的大小关系，需补全 
158         //将除法转化为减法 
159         if(a>=tmp)
160         {
161             a=bigsub(a,tmp);//a=a-tmp 
162             res=bigadd(res,restmp);//答案加上此时的倍数 
163         }
164         else
165         {
166             //a<tmp则/10 
167             tmp.erase(tmp.size()-1);
168             restmp.erase(restmp.size()-1);
169             inital(a,tmp);//将要判断a，tmp的大小关系，需补全 
170             //将除法转化为减法，同上 
171             if(a>=tmp)
172             {
173                 a=bigsub(a,tmp);
174                 res=bigadd(res,restmp);
175             }
176         }
177         inital(a,b);//将要判断下一轮的a，b大小关系，需补全 
178     }
179     cout<<res<<endl;
180 }
181 void fac(int n)
182 {
183     int num[10000];
184     memset(num,0,sizeof(num));
185     num[0]=1;//存储位数 
186     num[1]=1;//首位初值为1 
187     for(int i=1;i<=n;i++)
188     {
189         int len=num[0];
190         //每一位都乘i 
191         for(int j=1;j<=len;j++)
192         {
193             num[j]*=i;
194         }
195         for(int k=1;k<=num[0];k++)
196         {
197             //进位更新num[k]和num[k+1] 
198             if(num[k]>9)
199             {
200                 num[k+1]+=num[k]/10;
201                 num[k]=num[k]%10;
202             }
203             //进位后num[0]++ 
204             if(num[num[0]+1]!=0)
205             {
206                 num[0]++;
207             }
208         }
209     }
210     //遍历 
211     for(int i=num[0];i>=1;i--)
212     {
213         cout<<num[i];
214      } 
215      cout<<endl;
216 }
217 int main()
218 {
219     string a,b;
220     cin>>a>>b;
221     //bigadd(a,b);
222     //bigsub(a,b);
223     bigmul(a,b);
224     //bigdiv(a,b);
225     //int n;
226     //cin>>n;
227     //fac(n);
228  }