南昌理工ACM集训队
我感觉的高精度
高精其实就是换个方式存储数据，由于数据太大，longlong装不下，所以我们可以用数组来存储数据。就是用数组的一个的格子来存一个数（就存一个数）。
值得注意的问题就是进位（这个超级重要)
减法模板
我要评论//只能是两个正数相减，而且要大减小
/*string sub(string str1,string str2)
{
string str;
int tmp=str1.length()-str2.length();
int cf=0;
for(int i=str2.length()-1;i>=0;i--)
{
if(str1[tmp+i]<str2[i]+cf)
{
str=char(str1[tmp+i]-str2[i]-cf+'0'+10)+str;
cf=1;
}
else
{
str=char(str1[tmp+i]-str2[i]-cf+'0')+str;
cf=0;
}
}
for(int i=tmp-1;i>=0;i--)
{
if(str1[i]-cf>='0')
{
str=char(str1[i]-cf)+str;
cf=0;
}
else
{
str=char(str1[i]-cf+10)+str;
cf=1;
}
}
str.erase(0,str.find_first_not_of('0'));//去除结果中多余的前导0
return str;
}
除法模板
//两个正数相除，商为quotient,余数为residue
//需要高精度减法和乘法
void div(string str1,string str2,string "ient,string &residue)
{
quotient=residue="";//清空
if(str2=="0")//判断除数是否为0
{
quotient=residue="ERROR";
return;
}
if(str1=="0")//判断被除数是否为0
{
quotient=residue="0";
return;
}
int res=compare(str1,str2);
if(res<0)
{
quotient="0";
residue=str1;
return;
}
else if(res==0)
{
quotient="1";
residue="0";
return;
}
else
{
int len1=str1.length();
int len2=str2.length();
string tempstr;
tempstr.append(str1,0,len2-1);
for(int i=len2-1;i<len1;i++)
{
tempstr=tempstr+str1[i];
tempstr.erase(0,tempstr.find_first_not_of('0'));
if(tempstr.empty())
tempstr="0";
for(char ch='9';ch>='0';ch--)//试商
{
string str,tmp;
str=str+ch;
tmp=mul(str2,str);
if(compare(tmp,tempstr)<=0)//试商成功
{
quotient=quotient+ch;
tempstr=sub(tempstr,tmp);
break;
}
}
}
residue=tempstr;
}
quotient.erase(0,quotient.find_first_not_of('0'));
if(quotient.empty()) quotient="0";
}
加法和乘法用下面两个题目表示
1
题目描述
高精度加法，相当于a+b problem，不用考虑负数.
输入格式
分两行输入。a,b <=10^500
输出格式
输出只有一行，代表a+b的值
#include<bits/stdc++.h>
using namespace std;
int main()
{
char a[1002],b[1002];
bool x=false;//做标记
int c[1002],d[1002],e[1002],j;
memset(d,0,sizeof(d));
memset(e,0,sizeof(e));
memset(c,0,sizeof(c));//做初始化
cin >> a >> b;
int q=strlen(a),w=strlen(b);//算出数组的长度，这样方便往后的计算
for(int i=1;i<=q;i++) //把它变成整形，并把它的方向反一下，方便后面进位计算。
d[i]=a[q-i]-'0';
for(int i=0;i<=w;i++)
e[i]=b[w-i]-'0';
for(j=1;j<=max(q,w)+1;j++)//核心
{
c[j]+=d[j]+e[j];
if(c[j]>=10)//判断进位
{
c[j]%=10;
c[j+1]++;
}
}//加法运算
c[0]=j;
if(c[j+1]>0)
c[0]++;
for(int i=c[0];i>=1;i--)
{
if(c[i]==0&&x==false)//消前导零
continue;
x=true;
cout << c[i];
}
return 0;
}
2
题目描述
求两数的积。
输入格式
两行，两个整数。
输出格式
一行一个整数表示乘积。
说明/提示
每个数字不超过 10 ^2000，需用高精。
#include<bits/stdc++.h>
using namespace std;
int main()
{
bool x=false;
char a[40002],b[40002];
long long int c[4000002],d[4000002],e[4000002],j,h,k;
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
memset(e,0,sizeof(e));//初始化
cin >> a >> b;
int q=strlen(a),w=strlen(b);//计算字符串长度
for(int i=1;i<=q;i++)//转换类型，并反转
c[i]=a[q-i]-'0';
for(int i=1;i<=w;i++)
d[i]=b[w-i]-'0';
for(j=1;j<=q+1;j++)//核心，用两个循环是因为两个数组的每个元素在乘法里面都要相互乘一遍。
{
for(k=1;k<=w+1;k++)
{
e[k+j-1]+=c[j]*d[k];
if(e[k+j-1]>=10)//进位
{
h=e[k+j-1]/10;
e[j+k-1]%=10;
e[j+k]+=h;
}
}
}//乘法运算
e[0]=j*k;
if(e[j*k+1]>0)
e[0]++;
for(int i=e[0];i>=1;i--)
{
if(e[i]==0&&x==false)//消除前导零
continue;
x=true;
cout << e[i];
}
if(x==false)
cout << 0;
return 0;
}
本文地址：https://blog.csdn.net/qq_45709386/article/details/107880672
如对本文有疑问， 点击进行留言回复！！
【贪心】P1792 [国家集训队]种树 & P1484 种树
网友评论