介绍
高精度运算，是指参与运算的数(加数，减数，因子……)范围大大超出了标准数据类型(整型，实型)能表示的范围的运算。例如，求两个200位的数的和。这时，就要用到高精度算法了。
思想
就是将要参与运算的数以字符串的形式输入，将其倒着存入数组（即个位存在1位），然后用小学二年级数学的列式计算思想算出答案并倒着输出（即最高位第一个输出）
高精度加法
#include<iostream> #include<cstring> using namespace std; string a1,b1; int a[510]={0},b[510]={0},c[510]={0}; void init(string s,int x[]){x[0]=s.size();for(int i=1;i<=x[0];i++)x[i]=s[x[0]-i]-48;} int main(){cin>>a1>>b1;init(a1,a);init(b1,b); int an=a[0],bn=b[0],cn=1,x=0; while(cn<=an||cn<=bn)c[cn]=a[cn]+b[cn]+x,x=c[cn]/10,c[cn]%=10,cn++; c[cn]=x;while(!c[cn]&&cn>1)cn--;for(int i=cn;i>=1;i--)cout<<c[i];}
高精度减法
#include<cstdio> #include<iostream> #include<string> #define M 10010 using namespace std; string s1,s2;int aa[M],bb[M],c[M]; void init(string s,int x[]){x[0]=s.size();for(int i=1;i<=x[0];i++)x[i]=s[x[0]-i]-48;} void work(int a[],int b[]){int cn=1; while(cn<=a[0]||cn<=b[0]){if(a[cn]<b[cn])a[cn+1]--,a[cn]+=10; c[cn]=a[cn]-b[cn];cn++;} while(!c[cn]&&cn>1)cn--;for(int i=cn;i>=1;i--)printf("%d",c[i]);} int main(){cin>>s1>>s2;init(s1,aa);init(s2,bb); (aa[0]<bb[0])?printf("-"),work(bb,aa):work(aa,bb);}
高精度乘法
#include<cstdio> #include<string> #include<iostream> using namespace std; #define M 10010 #define fr(i,b) for(int i=1;i<=b;i++) #define fd(i,b) for(int i=b;i>=1;i--) string s1,s2;int a[M],b[M],c[M]; void init(string s,int x[]){x[0]=s.size();fr(i,x[0])x[i]=s[x[0]-i]-48;} int main(){cin>>s1>>s2;init(s1,a);init(s2,b); fr(i,a[0]){int x=0; fr(j,b[0])c[i+j-1]=a[i]*b[j]+x+c[i+j-1],x=c[i+j-1]/10,c[i+j-1]%=10; c[i+b[0]]=x;} c[0]=a[0]+b[0];while(!c[c[0]]&&c[0]>1)c[0]--; fd(i,c[0])printf("%d",c[i]);return 0;}
高精度除法
高精除整数
#include<cstdio> #include<iostream> #include<cstring> using namespace std; #define fr(i,a,b) for(int i=a;i<=b;i++) string s;long long b;int a[5050],c[5050]; int main(){cin>>s>>b;int x=0,cn=1; a[0]=s.size();fr(i,1,a[0])a[i]=s[i-1]-48; fr(i,1,a[0])c[i]=(x*10+a[i])/b,x=(x*10+a[i])%b; while(!c[cn]&&cn<a[0])cn++;fr(i,cn,a[0])printf("%d",c[i]);return 0;}
高精度除法
#include <iostream> #include <cstring> #include <cstdio> #define M 35000 #define fd(i,b) for(int i=b;i>=1;i--) #define fr(i,b) for(int i=1;i<=b;i++) using namespace std; string a1,b1;int a[M],b[M],c[M],t[M],g=0; int cmp(int x[],int y[]){if(x[0]!=y[0])return x[0]>y[0]?1:-1; fd(i,x[0])if(x[i]!=y[i])return x[i]>y[i]?1:-1;return 0;} void change(int x[],int y[],int l){fr(i,x[0])y[i+l-1]=x[i];y[0]=x[0]+l-1;} void init(string s,int x[]){cin>>s;x[0]=s.size();fr(i,x[0])x[i]=s[x[0]-i]-48;} int main(){init(a1,a);init(b1,b);c[0]=a[0]-b[0]+1; fd(i,c[0]){memset(t,0,sizeof(t));change(b,t,i); while(cmp(a,t)>=0){c[i]++; if(!cmp(a,t)){a[0]=0;continue;} fr(i,a[0]){if(a[i]<t[i])a[i+1]--,a[i]+=10;a[i]-=t[i];} while(a[0]>0&&!a[a[0]])a[0]--;}} while(!c[c[0]]&&c[0]>0)c[0]--; if(!c[0])printf("0");else fd(i,c[0])printf("%d",c[i]);return 0; }
全高精度重载模板
#include<vector> #include<iostream> #include<cstring> #include<cmath> #include<cstdio> using namespace std; #define ct register int #define fr(a,b,c) for(ct a=b;a<=c;a++) #define fd(a,b,c) for(ct a=b;a>=c;a--) struct ll {static const int BASE=100000000,WIDTH=8; vector<long long>s; ll(){*this=0;}ll(const int& num){*this=num;} ll operator = (int num){s.clear();do {s.push_back(num%BASE);num/=BASE;} while(num>0);return *this;} ll operator = (const string& str) {s.clear(); int x,len=(str.length()-1)/WIDTH+1; fr(i,0,len-1){int end=str.length()-i*WIDTH,start=max(0,end-WIDTH); sscanf(str.substr(start,end-start).c_str(),"%lld",&x); s.push_back(x);}return *this;} bool operator < (const ll& b){ if(s.size()!=b.s.size())return s.size()<b.s.size()?1:0; fd(i,s.size()-1,0)if(s[i]!=b.s[i])return s[i]<b.s[i]?1:0; return 0;} bool operator >=(const ll& b){return !(*this<b);} bool operator ==(const ll& b){if(s.size()!=b.s.size())return 0; fr(i,0,s.size()-1)if(s[i]!=b.s[i])return 0;return 1;} ll operator + (const ll& b){ll c;c.s.clear(); for(int i=0,g=0;;i++){if(g==0&&i>=s.size()&&i>=b.s.size())break; int x=g;if(i<s.size())x+=s[i];if(i<b.s.size())x+=b.s[i]; c.s.push_back(x%BASE);g=x/BASE;}return c;} ll operator - (const ll& b){ll c;c=*this; fr(i,0,c.s.size()-1){int tmp;tmp=i>=b.s.size()?0:b.s[i]; if(c.s[i]<tmp)c.s[i+1]-=1,c.s[i]+=BASE;c.s[i]-=tmp;} while(!c.s.back()&&c.s.size()>1)c.s.pop_back();return c;} void operator -= (const ll& b){*this=*this-b;} ll operator * (const ll& b){ll c; c.s.resize(s.size()+b.s.size()); fr(i,0,s.size()-1)fr(j,0,b.s.size()-1)c.s[i+j]+=s[i]*b.s[j]; fr(i,0,c.s.size()-2)c.s[i+1]+=c.s[i]/BASE,c.s[i]%=BASE; while(!c.s.back()&&c.s.size()>1)c.s.pop_back();return c;} friend istream& operator >> (istream& input,ll& x){string s; if(!(input>>s))return input;x=s;return input;} friend ostream& operator << (ostream& output,const ll& x){output<<x.s.back(); fd(i,x.s.size()-2,0){char buf[20];sprintf(buf,"%08d",x.s[i]); fr(j,0,strlen(buf)-1)output<<buf[j];}return output;} }; ll Copy(const ll& b,int x){ll t;t.s.resize(b.s.size()+x); fr(i,0,b.s.size()-1)t.s[i+x]=b.s[i];return t;} ll Divide(const ll& a,const ll& b,ll& mod){ll c; c.s.resize(a.s.size()-b.s.size()+1);mod=a; int Pow[(int)log2(ll::BASE)+5];Pow[0]=1; fr(i,1,log2(ll::BASE))Pow[i]=Pow[i-1]*2; fd(i,c.s.size()-1,0){ll t;t=Copy(b,i); fd(j,log2(ll::BASE),0) if(mod>=t*Pow[j])c.s[i]+=Pow[j],mod-=t*Pow[j]; }while(!c.s.back()&&c.s.size()>1)c.s.pop_back();return c; }ll a,b,c,d; int main(){cin>>a>>b; if(a<b)cout<<a+b<<endl<<'-'<<b-a<<endl<<a*b<<endl<<0<<endl<<a<<endl; else c=Divide(a,b,d),cout<<a+b<<endl<<a-b<<endl<<a*b<<endl<<c<<endl<<d<<endl; return 0;}