高精度算法

    通常，我们在处理问题的时候，很多的数据并不像我们所熟知的int 和long long一样，很容易的能被表达出来。特别是我们现在这个答案数据的时代，我们时常会遇见很多高精度的数据，有时要对它们进行操作就会很困难。

    于是乎，我们引入了高精度算法：

    我们先总结一下高精度算法的一些特性：

    ·首先高精度计算，我们肯定要把按字符串读入的数字转化成真正的数字，并且为了统一加减乘除，我们把它们倒着存入一个vector；

    ·然后是我们会依据真实计算的方法，都是按位进行计算；

    ·值得注意的是，对于加法我们用t表示进位，对于减法，我们用t表示借一位，对于除法，我们用r表示当前余数，最后返回一个vector数组

    ·还要注意，高精度的乘除法，需要去掉前导零！

    //接下来上板子：

   //高精度加法：

#include

using namespace std;

vector add(vector &a,vector &b){
vector ans;
int t=0;
for(int i=0;i
if(i
if(i
ans.push_back(t%10);
t/=10;
}
if(t) ans.push_back(t);
return ans;
}

int main()
{
string str1,str2;
cin>>str1>>str2;
vector a,b;
for(int i=str1.size()-1;i>=0;i--) a.push_back(str1[i]-'0');
for(int i=str2.size()-1;i>=0;i--) b.push_back(str2[i]-'0');
vector ans = add(a,b);
for(int i=ans.size()-1;i>=0;i--) printf("%d",ans[i]);
return 0;
}

   //高精度减法

#include

using namespace std;

vector sub(vector& a,vector& b){
vector ans;
int t=0;
for(int i=0;i
t=a[i]-t;
if(i
ans.push_back((t+10)%10);           //注意这个push值的方式
if(t<0) t=1;
else t=0;
}
while(ans.size()>1 && ans.back()==0) ans.pop_back();        //去掉前导零
return ans;
}

int main()
{
string a,b;
cin>>a>>b;
vector va,vb,ans;
for(int i=a.size()-1;i>=0;i--) va.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;i--) vb.push_back(b[i]-'0');

if(a.size()
printf("-");
ans=sub(vb,va);
}
else ans=sub(va,vb);
for(int i=ans.size()-1;i>=0;i--) printf("%d",ans[i]);
return 0;
}

     //高精度乘法

#include

using namespace std;

vector mul(vector a,int b){
int t=0;
vector ans;
for(int i=0;i
t+=(a[i]*b);
ans.push_back(t%10);
t/=10;
}
if(t) ans.push_back(t);                  //如果t还有值就也要push
return ans;
}

int main()
{
string str;
int b;
cin>>str>>b;
vector a;
for(int i=str.size()-1;i>=0;i--) a.push_back(str[i]-'0');
if(b==0) printf("0");
else{
vector ans=mul(a,b);
for(int i=ans.size()-1;i>=0;i--) printf("%d",ans[i]);
}
return 0;
}

    //高精度除法

#include

using namespace std;

void div(vector& a,int b){
vector ans;
int r=0;
for(int i=a.size()-1;i>=0;i--){                                           //除法是要从高位向低位遍历
r=r*10+a[i];
ans.push_back(r/b);
r%=b;                                                                             //push商，mod余数
}
while(ans.size()>1 && ans.front()==0) ans.erase(ans.begin());                     //去除前导零
for(int i=0;i
printf("\n");
printf("%d",r);
return;
}

int main()
{
string a;
int b;
cin>>a>>b;
vector va;
for(int i=a.size()-1;i>=0;i--) va.push_back(a[i]-'0');
div(va,b);
return 0;
}