高精度
平时我们对于加减乘除是直接使用+-*/来实现的，但当数的长度来到100、1000时，int、long long的存储范围就不够了，此时就是使用高精度的时候。
1. 高精度加法 A+B
1.1 运算原理
首先是大数之间的加法，可以模拟我们正常进行加法的步骤来进行运算。例如下图：
可以发现加法运算是从后向前进行的，所以我们可以reverse将获得的大数倒序，运算完毕后再使其正序输出。
1.2 例题
参考代码：
void solve(){ //... for(int i=0,c=0;i<max(a.length(),b.length()) || c;i++){ int t1=0,t2=0; if(i<a.length()) t1 = a[i]-'0'; if(i<b.length()) t2 = b[i]-'0'; int t = t1 + t2 + c; c = t / 10;t %= 10; ans.push_back(t+'0'); } //...}2. 高精度减法 A-B
2.1 运算原理
其次是大数之间的减法，具体方法依然类似于大数加法，不同的是由于AB大小的不同会导致结果负数的出现，此时我们可以使A-B = -(B-A)让减法的结果始终保持为正。
P.S. 注意由于是减法，可能会导致前导零的出现，注意在输出前去除。
2.2 例题
参考代码：
bool comp(){ if(a.length()!=b.length()) return a.length()>b.length(); for(int i=a.length()-1;~i;i--) if(a[i]!=b[i]) return a[i]>b[i]; return true;}void solve(){ //... if(!comp()) p = 1,swap(a,b); for(int i=0,c=0;i<a.length();i++){ int t1=0,t2=0; if(i<a.length()) t1 = a[i]-'0'; if(i<b.length()) t2 = b[i]-'0'; int t = t1 - t2 + c; if(t < 0) c=-1,t+=10; else c = 0; ans.push_back(t+'0'); }reverse(ans.begin(),ans.end()); if(p) cout<<"-";p=-1; while(++p<ans.length() && ans[p]=='0'); ans = ans.substr(min(p,(int)(ans.length()-1)),max((int)(ans.length()-p),1)); //...}3. 高精度乘法 A*b
3.1 运算原理
大数与小数之间的乘法较简单，用一个数来记录A每位数与b乘积和的剩余值，依次得到每位的运算结果即可。
P.S. 注意当大数为0时，其乘积可能会有前导零，注意去除。
3.2 例题
参考代码：
void solve(){ for(int i=0,c=0;i<a.length() || c;i++){ int t1 = 0; if(i<a.length()) t1 = a[i]-'0'; int t = t1 * b + c; ans.push_back(t%10+'0');c = t / 10; }}4. 高精度除法 A/b
4.1 运算原理
同大数与小数的乘法，大数和小数的除法同样较为简单。此时可以从大数前段依次向后除以b，依次记录前段和c除以b的商和余数即可。
P.S. 注意由于在运算较前期可能由于被除数过小导致前导零的出现，注意在输出前去除。
4.2 例题
参考代码：
void solve(){ for(int i=0;i<a.length();i++){ int t1 = a[i]-'0'; int t = t1 + 10 * c; ans.push_back(t/b + '0'); c = t%b; }int p = -1;while(++p<ans.length() && ans[p]=='0'); ans = ans.substr(min(p,(int)(ans.length()-1)),max(1,(int)(ans.length()-p)));}High-precision
Normally we implement addition, subtraction, multiplication, and division directly using +-*/, but when the numbers grow to lengths of 100 or 1000, the storage range of int and long long is no longer sufficient; at this point it is time to use high-precision.
1. High-precision addition A+B
1.1 How it works
First is addition between large numbers, which can be simulated by following the normal steps of addition. For example, see the figure below:
You can see that addition is performed from right to left, so we can reverse the obtained digits to invert their order, and after computation output in forward order.
1.2 Examples
Reference code：
void solve(){ //... for(int i=0,c=0;i<max(a.length(),b.length()) || c;i++){ int t1=0,t2=0; if(i<a.length()) t1 = a[i]-'0'; if(i<b.length()) t2 = b[i]-'0'; int t = t1 + t2 + c; c = t / 10;t %= 10; ans.push_back(t+'0'); } //...}2. High-precision subtraction A-B
2.1 How it works
Next is subtraction between large numbers. The method is still similar to high-precision addition; the difference is that due to the relative sizes of A and B, the result may be negative. In that case we can write A-B = -(B-A) to keep the subtraction result non-negative.
P.S. Note that because this is subtraction, leading zeros may appear; remember to remove them before output.
2.2 Examples
Reference code：
bool comp(){ if(a.length()!=b.length()) return a.length()>b.length(); for(int i=a.length()-1;~i;i--) if(a[i]!=b[i]) return a[i]>b[i]; return true;}void solve(){ //... if(!comp()) p = 1,swap(a,b); for(int i=0,c=0;i<a.length();i++){ int t1=0,t2=0; if(i<a.length()) t1 = a[i]-'0'; if(i<b.length()) t2 = b[i]-'0'; int t = t1 - t2 + c; if(t < 0) c=-1,t+=10; else c = 0; ans.push_back(t+'0'); }reverse(ans.begin(),ans.end()); if(p) cout<<"-";p=-1; while(++p<ans.length() && ans[p]=='0'); ans = ans.substr(min(p,(int)(ans.length()-1)),max((int)(ans.length()-p),1)); //...}3. High-precision multiplication A*b
3.1 How it works
Multiplication between a large number and a small number is relatively straightforward: use a variable to record the carry of the products of each digit of A with b, and obtain the result for each digit in sequence.
P.S. Note that when the large number is 0, the product may have leading zeros; be sure to remove them.
3.2 Examples
Reference code：
void solve(){ for(int i=0,c=0;i<a.length() || c;i++){ int t1 = 0; if(i<a.length()) t1 = a[i]-'0'; int t = t1 * b + c; ans.push_back(t%10+'0');c = t / 10; }}4. High-precision division A/b
4.1 How it works
Similar to the multiplication of large numbers by small numbers, the division of a large number by a small number is also straightforward. You can divide the leading part of the large number from left to right by b, recording the quotient and remainder of each prefix with c/b.
P.S. Note that in earlier stages the dividend may be too small, causing leading zeros; remember to remove them before output.
4.2 Examples
Reference code：
void solve(){ for(int i=0;i<a.length();i++){ int t1 = a[i]-'0'; int t = t1 + 10 * c; ans.push_back(t/b + '0'); c = t%b; }int p = -1;while(++p<ans.length() && ans[p]=='0'); ans = ans.substr(min(p,(int)(ans.length()-1)),max(1,(int)(ans.length()-p)));}高精度演算
普段、加算・減算・乗算・除算は直接+-*/を使って実現しますが、数の長さが100や1000になると、intやlong longの格納範囲では足りなくなります。そんな時こそ高精度を使う時です。
1. 高精度加算 A+B
1.1 演算原理
まずは大きな数同士の加算です。通常の加算の手順を模して計算します。例えば下の図のように：
加算は後ろから前に向かって行われることが分かります。なので得られた大数をreverseして逆順にし、計算が終わったら正順に出力します。
1.2 例題
参考コード：
void solve(){ //... for(int i=0,c=0;i<max(a.length(),b.length()) || c;i++){ int t1=0,t2=0; if(i<a.length()) t1 = a[i]-'0'; if(i<b.length()) t2 = b[i]-'0'; int t = t1 + t2 + c; c = t / 10;t %= 10; ans.push_back(t+'0'); } //...}2. 高精度減算 A-B
2.1 演算原理
次に大きな数同士の減算です。具体的な方法は依然として大数加算と似ていますが、ABの大きさの差により結果が負になることがあります。その場合、A-B = -(B-A)として減算の結果を常に正に保つことができます。
P.S. 減算のため先頭ゼロが出現することがあります。出力前に除去してください。
2.2 例題
参考コード：
bool comp(){ if(a.length()!=b.length()) return a.length()>b.length(); for(int i=a.length()-1;~i;i--) if(a[i]!=b[i]) return a[i]>b[i]; return true;}void solve(){ //... if(!comp()) p = 1,swap(a,b); for(int i=0,c=0;i<a.length();i++){ int t1=0,t2=0; if(i<a.length()) t1 = a[i]-'0'; if(i<b.length()) t2 = b[i]-'0'; int t = t1 - t2 + c; if(t < 0) c=-1,t+=10; else c = 0; ans.push_back(t+'0'); }reverse(ans.begin(),ans.end()); if(p) cout<<"-";p=-1; while(++p<ans.length() && ans[p]=='0'); ans = ans.substr(min(p,(int)(ans.length()-1)),max((int)(ans.length()-p),1)); //...}3. 高精度乘法 A*b
3.1 演算原理
大数と小数の乗算は比較的単純で、Aの各桁とbの積和の残りを1つの値で記録します。順に各桁の計算結果を得るだけです。
P.S. 大きな数が0の時は積の先頭ゼロが出ることがあります。取り除いてください。
3.2 例題
参考コード：
void solve(){ for(int i=0,c=0;i<a.length() || c;i++){ int t1 = 0; if(i<a.length()) t1 = a[i]-'0'; int t = t1 * b + c; ans.push_back(t%10+'0');c = t / 10; }}4. 高精度除法 A/b
4.1 演算原理
同大数と小数の乘法、大数と小数の除法も同様に比較的簡単です。此時は大数の前半から順に後ろへ除いていき、前段とcをbで割った商と余りを順次記録します。
P.S. 初期の演算で被除数が小さすぎて先頭ゼロが出現することがあります。出力前に取り除いてください。
4.2 例題
参考コード：
void solve(){ for(int i=0;i<a.length();i++){ int t1 = a[i]-'0'; int t = t1 + 10 * c; ans.push_back(t/b + '0'); c = t%b; }int p = -1;while(++p<ans.length() && ans[p]=='0'); ans = ans.substr(min(p,(int)(ans.length()-1)),max(1,(int)(ans.length()-p)));}部分信息可能已经过时