总述 （tip: ÷为整除

数据的接收与存储方法

输入的数值没爆范围时，可用数值型变量来接收。但爆了以后，可采用字符串方式

• 利用字符串函数和操作运算
• 直接用循环加数组 输入数据

数串“字符串”形式输入数据，并将其转化为数组来存储

高精度位数的确定

接收时往往采用字符串，所以它的位数就 = 字符串长度。

1. 两数之和的位数最大为较大的数的位数+1
2. 乘积的位数最大为两个因子的位数之和
3. 阶乘与乘方的位数可以采用对数运算来确定计算结果的位数

进位处理和借位处理

• 加法的

c[i] = a[i] + b[i];
if (c[i] >= 10)
{
    c[i] = c[i] % 10;
    c[i + 1] = c[i + 1] + 1;
}

• 减法的

if (a[i] < b[i])
{
    a[i + 1] -=  1;
    a[i] += 10;
}
c[i] = a[i] - b[i];

• 乘法的

c[i + j - 1] = a[i] * b[j] + x + c[i + j - 1];
x = c[i + j - 1] / 10;
c[i + j - 1] = c[i + j - 1] % 10;

• 商和余数

视被除数和除数的位数情况进行处理

• 高精度$\div$单精度 从高位相除取余数
• 高精度$\div$高精度 再用高精度减法，再统计相减次数

存储输出的$N + 1$位数字

结果的输出

小数点的位置、处理多于的0

---

高精度加法

要解决的问题：

• 数据的输入
• 数据的存储
• 加法运算，注意进位处理
• 结果的输出

高精度数的输入和保存

输入要符合数字的输入规律：连续输入，中间无空格。字符串读入，数组保存。

cin >> s1 >> s2;
la = s1.size();
lb = s2.size();
for (int i = la - 1; i >= 0; i--) a[la - i - 1] = s1[i] - '0';
for (int i = lb - 1; i >= 0; i--) b[lb - i - 1] = s2[i] - '0';//从0开始

加法运算时的进位

if(la > lb) len = la;
else len = lb; //len是较大位数

m = 0;//进位

方法一：

for (int i = 0; i < len; i++)
{
	c[i] = (a[i] + b[i] + m) % 10;
    m = (a[i] + b[i] + m) / 10;
}
    //最后一个进位m的处理
if (m > 0)//m = 1
{
	c[len++] = m;
}   

方法二

for (int j = 0; j < len; j++)//先逐位相加
{
    c[i] = a[i] + b[i];
}

for (int i = 0; i < len; i++)//从低位依次处理低位
{
    c[i + 1] += c[i] / 10;
    c[i] %= 10;
}
if (c[len + 1] > 0) len = len + 1;//进位

​

方法三

//a = a + b; 节省空间，省去数组c
for (int i = 0; i < len; i++)
{
    a[i + 1] += (a[i] + b[i]) / 10;
    a[i] = (a[i] + b[i]) % 10;
}
if (a[len + 1] > 0) len +=  1; 

运算结果的输出

• for (int i = len - 1; i >= 0; i--)

• for (int i = len - 1; i >= 1; i--)

• cout << c[0]

如果数据变态的出了0001和0002这样的话……

for (int j = len - 1; j >= 0; j--)
{
    if (c[j] == 0)
        t++;
    if (c[j] != 0)
        break;
}

if (t == len) //放置判0把答案0删除
{
    cout << 0 << endl;
    return 0;
}

for (int i = len - 1 - t; i >= 0; i--)//判0
{
    cout << c[i];
}

---

高精度减法

需要解决的问题

1. 比较 $a$ 和 $b$ 的大小 从而确定结果的正负号
2. 借位问题
3. 去掉结果前面多余的0

具体步骤

1. 比较 $a$ 和 $b$ 的大小 确定结果的正负号 谁减谁

cin >> s1 >> s2;
if (s1 == s2) 
{
	cout << "0" << endl;
    return 0;
}

la = s1.size();
lb = s2.size();

if (la < lb || ((la == lb) && (s1 < s2)))
{
	fh = '-';
    s = s1;
    s1 = s2;
    s2 = s;
}


la = s1.size();
lb = s2.size();//la绝对值大 

for (int i = la - 1; i >= 0; i--) a[la - i - 1] = s1[i] - '0';
for (int i = lb - 1; i >= 0; i--) b[lb - i - 1] = s2[i] - '0';
k = la - 1;//数组从0开始

2. 借位问题 $a = a-b$

for (int t = 0; t < la; t++)
{
	if (a[t] < b[t])
	{
		a[t + 1] -= 1;
		a[t] += 10;
	}
	a[t] -= b[t];
}

3. 去掉结果前面多余的$0$

while (a[k] == 0) k--;

---

高精度乘法

单精度×高精度

方法

1. $a$ 的每一位都单独与 $b$ 相乘
2. 由低到高位依次再处理 $a$ 的进位
3. 处理最高位

参考程序

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

long long b, m;
long long a[260];

int main()
{
    int len;
    string s;

    cin >> s >> b;

    if (b == 0 || s == "0")
    {
        cout << 0 << endl;
        return 0;
    }

    len = s.size();

    for (int i = 1; i <= len; i++)
        a[i] = s[len - i] - '0';


    for (int i = 1; i <= len; i++)
        a[i] *= b;//逐位乘b

    for (int k = 1; k <= len; k++) //处理进位
    {
        a[k + 1] += a[k] / 10;
        a[k] = a[k] % 10;
    }

    m = a[len + 1];

    while (m)
    {
        len++;
        a[len] = m % 10;
        m /= 10;
    }

    for (int y = len; y >= 1; y--)    cout << a[y];

    return 0;
}

---

高精度×高精度

见板子

---

高精度除法

高精度÷单精度

1. 输入与储存

单精度可以直接读入，高精度的输入与存储同加法运算，仍用$a[1]$存储数的个位

2. 计算结果的位数

除法运算的结果的位数最大等于被除数的位数

3. 除法计算以及商与余数的处理

参与运算的数据：

• 1个不变的数：除数 $b$

• 3个变化的数：被除数 $a$、商 $c$ 和余数 $d$

  已知被除数（高精度数）存储在数组$a$中，$a[1]$放的是被除数的个位，$a[len]$放的是被除数的最高位，根据除法运算的规则，应该从被除数的最高位开始除以除数，采取按位相处的方法

  商 $c[len]=a[len]\div b$

  余数 $d=a[len]$ % $b$

  将 $d\times 10 + a[len - 1]$ 重新作为被除数，再继续以上步骤，直到被除数（$a$） 的每一位都除完为止

  过程如下：

d = 0;
for (int i = len; i >= 1; i--)
{
    d = d * 10 + a[i];
    c[i] = d / b;//商
    d = d % b;//余数
}

4.结果的输出

商放在数组 $c$ 中，注意商中要去掉高位的0，确定好输出的位置，余数直接输出 $d$ 即可

参考程序

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
	const int maxn = 2000;
	string sa;//被除数
	int b, d;//b为除数，d为余数
	int la, len;
	int a[maxn], c[maxn];
	
	cin >> sa >> b;
	
	la = sa.size();
	
	for (int i = la; i >= 1; i--)
	{
	    a[la - i + 1] = sa[i - 1] - '0';
	}
	
	len = la;
	d = 0;
	
	for (int i = len; i >= 1; i--)
	{
	    d = d * 10 + a[i];
	    c[i] = d / b;//商
	    d = d % b;//余数
	}
	
	while (len >= 1 && c[len] == 0)
	    len--;
	
	for (int k = len; k >= 1; k--)
	{
	    cout << c[k];
	}
//	if (d) cout << '.' << d << endl;

    return 0;
}

在做两个高精度数运算时，存储高精度数的数组元素可以不仅仅只保留一个数字，而采取保留多位数

这样，在做运算（特别是乘法运算）时，可以减少很多操作次数

高精度÷高精度

1. 输入与储存

仍用$a[1]$存储数的个位

2. 计算结果的位数

除法运算的结果的位数最大等于被除数的位数

3. 除法计算

   可采用循环相减的方法，利用高精度减法来实现

   • 初始化余数 $d$,将被除数的最高位 $a[len]$ 的值赋给余数 $d$ 的第 $1$ 位 $d[1]$
   • 比较余数 $d$ 和除数 $b$ 的大小。
     • $d < b$ ：$d\times 10$（高精度乘法），并将被除数的下一个取数（$a[len - 1]$）再赋给余数$d$的第$1$位$d[1]$
     • $d\geq b$ ：跳出这步，继续
   • 计算$d=d-b$（高精度减法）,并将商$c$的当前位$c[i] + 1$ ,判断是否$d\geq b$
     • 是：继续上一步
     • 否：得到商的一位
   • 返回第二步，继续
   • 直至将被除数a的所有数取完并求减法结束为止

参考程序

#include <iostream>  
#include <cstring>  
#include <cstdio>  

using namespace std;

const int N = 100001;
int a[N], b[N], res[N * 2];
char x[N], y[N];
int la, lb;

void init()
{
	la = strlen(x);
	lb = strlen(y);
	memset(a,0,sizeof(a));  
    memset(b,0,sizeof(b)); 
    memset(res,0,sizeof(res)); 
    
    for (int i = la - 1; i >= 0; i--) a[la - i - 1] = x[i] - '0';
    for (int i = lb - 1; i >= 0; i--) b[lb - i - 1] = y[i] - '0'; //从0开始
}

int substraction(int *p1,int *p2,int len1,int len2)
//计算长度为len1的大整数减去长度为len2的大整数的结果的长度 
{
	//减的结果放在数组p1中，不够返回-1,正好返回0 
	if (len1 < len2) return -1;
	bool flag = 0;
	if (len1 == len2)
	{
		for (int i = len1 - 1; i >= 0; i--)
		{
			if (p1[i] > p2[i]) flag = 1;
			else if (p1[i] < p2[i])
			{
				if (!flag) return -1;
			}
		}
	}
	
	for (int i = 0; i < len1; i++)
	{
		p1[i] -= p2[i];
		if (p1[i] < 0)
		{
			p1[i] += 10;
			p1[i + 1]--;
		}
	}
	for (int i = len1 - 1; i >= 0; i--)
	{
		if (p1[i]) return i + 1;
	}
	return 0;
}

void output()
{
	for (int i = 0; i < N; i++)
	{
		if (res[i] >= 10)//进位 
		{
			res[i + 1] += res[i] / 10;
			res[i] %= 10;
		}
	}
	
	bool flag = 0;
	for (int i = N - 1; i >= 0; i--)
	{
		if (flag) cout << res[i];
		else if (res[i])
		{
			cout << res[i];
			flag = 1;
		}
	}
	
	if (!flag) cout << 0;
	
	cout << endl;
}

void divv()
{
	init();
	
	if (la < lb)
	{
		cout << 0 << endl;
		return;
	}
	
	la = substraction(a, b, la, lb);
	if (la < 0)
	{
		cout << 0 << endl;
		return;
	}
	else if (la == 0)
	{
		cout << 1 << endl;
		return;
	}
	
	res[0]++;//减掉一次了，商+1
	int k = la - lb;
	if (k < 0)//减一次后不能再减了 
	{
		output();
		return;
	}
	else if (k > 0)//将数组b乘以10的某次幂，使得其长度与数组a相同
	{
		for (int i = la - 1; i >= 0; i--)
		{
			if (i >= k) b[i] = b[i - k];
			else b[i] = 0;
		}
	}
	
	lb = la;
	for (int i = 0; i <= k; i++)//先减去若干个b*(10^k)，不够减了再减去若干个b*(10^(k-1))
	{
		int temp;
		while ((temp = substraction(a, b + i, la, lb - i)) >= 0)//一直减到不够减为止
		{
			la = temp;
			res[k - i]++; //每成功减一次，则商的相应位+1
		}
	}
	output();
}

int main()
{
	scanf("%s %s", x, y); 
	divv();
	//init();
	//for (int i = 0; i < la; i++) cout << a[i];
	return 0;
}

---

#include <iostream>  
#include <cstring>  
#include <cstdio>  

using namespace std;

const int N = 100001;
int a[N], b[N], res[N * 2];
char x[N], y[N];
int la, lb;

void init()
{
	la = strlen(x);
	lb = strlen(y);
	memset(a,0,sizeof(a));  
    memset(b,0,sizeof(b)); 
    memset(res,0,sizeof(res)); 
    
    for (int i = la - 1; i >= 0; i--) a[la - i] = x[i] - '0';
    for (int i = lb - 1; i >= 0; i--) b[lb - i] = y[i] - '0';//从1开始
}

int substraction(int *p1,int *p2,int len1,int len2)
//计算长度为len1的大整数减去长度为len2的大整数的结果的长度 
{
	//减的结果放在数组p1中，不够返回-1,正好返回0 
	if (len1 < len2) return -1;
	bool flag = 0;
	if (len1 == len2)
	{
		for (int i = len1; i >= 1; i--)
		{
			if (p1[i] > p2[i]) flag = 1;
			else if (p1[i] < p2[i])
			{
				if (!flag) return -1;
			}
		}
	}
	
	for (int i = 1; i <= len1; i++)
	{
		p1[i] -= p2[i];
		if (p1[i] < 0)
		{
			p1[i] += 10;
			p1[i + 1]--;
		}
	}
	for (int i = len1; i >= 1; i--)
	{
		if (p1[i]) return i;
	}
	return 0;
}

void output()
{
	for (int i = 1; i <= N; i++)
	{
		if (res[i] >= 10)//进位 
		{
			res[i + 1] += res[i] / 10;
			res[i] %= 10;
		}
	}
	
	bool flag = 0;
	for (int i = N; i >= 1; i--)
	{
		if (flag) cout << res[i];
		else if (res[i])
		{
			cout << res[i];
			flag = 1;
		}
	}
	
	if (!flag) cout << 0;
	
	cout << endl;
}

void divv()
{
	init();
	
	if (la < lb)
	{
		cout << 0 << endl;
		return;
	}
	
	la = substraction(a, b, la, lb);
	if (la < 0)
	{
		cout << 0 << endl;
		return;
	}
	else if (la == 0)
	{
		cout << 1 << endl;
		return;
	}
	
	res[1]++;//减掉一次了，商+1
	int k = la - lb;
	if (k < 0)//减一次后不能再减了 
	{
		output();
		return;
	}
	else if (k > 0)//将数组b乘以10的某次幂，使得其长度与数组a相同
	{
		for (int i = la; i >= 1; i--)
		{
			if (i > k) b[i] = b[i - k];
			else b[i] = 0;
		}
	}
	
	lb = la;
	for (int i = 0; i <= k; i++)//先减去若干个b*(10^k)，不够减了再减去若干个b*(10^(k-1))
	{
		int temp;
		while ((temp = substraction(a, b + i, la, lb - i)) >= 0)//一直减到不够减为止
		{
			la = temp;
			res[k - i + 1]++; //每成功减一次，则商的相应位+1
		}
	}
	output();
}

int main()
{
	scanf("%s %s", x, y); 
	divv();
	//init();
	//for (int i = 0; i < la; i++) cout << a[i];
	return 0;
}