高精度

南昌理工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 &quotient,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