大数运算

---

1、简介

我们知道，在数学中，数值的大小是没有上限的，但是在计算机中，由于字长的限制，计算机所能表示的范围是有限的，当我们对比较小的数进行运算时，如：1234 + 5678，这样的数值并没有超出计算机的表示范围，所以可以运算。但是当我们在实际的应用中进行大量的数据处理时，会发现参与运算的数往往超过计算机的基本数据类型的表示范围，比如说，在天文学上，如果一个星球距离我们为 100 万光年，那么我们将其化简为公里，或者是米的时候，我们会发现这是一个很大的数。这样计算机将无法对其进行直接计算。
可能我们认为实际应用中的大数也不过就是几百位而已，实际上，在某些领域里，甚至可能出现几百万位的数据进行运算，这是我们很难想象的。如果没有计算机，那么计算效率可想而知。

由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。大数运算主要有加、减、乘三种方法（除法运算可以通过递归或者循环结合着栈来进行求解）。下面将分别予以介绍如何通过算法与数据结构来完成这三类运算。

---

2、加法运算

1. 高精度加法运算的数理过程

为便于分析与理解，我们先回顾下多位数加法的流程（如下图所示）：

该过程会从数的最低位开始依次往高位进行计算，具体的加数过程为：

• $6+9=15>10$，因此会发生进位，原位保留加法结果对 $10$ 的余数，即 $15\%10=5$。
• $5+8+1=14>10$（其中的 $+1$ 由较低位进位所得），因此会发生进位，原位保留 $14\%10=4$。
• $4+7+1=12>10$（其中的 $+1$ 由较低位进位所得），因此会发生进位，原位保留 $12\%10=2$。
• $3+1=4<10$（其中的 $+1$ 由较低位进位所得），不会发生进位，原位保留 $4$。
• $2+0=2<10$，不会发生进位，原位保留 $2$。
• $1+0=1<10$，不会发生进位，原位保留 $1$。

所有位均计算完毕，最终得到和为：$124245$。

这便是多位数加法的执行过程，这对具有高精度的大数也适用。由于在加法过程中涉及到对各个位的加法运算，因此在处理大数的加法运算时，通常会用一个 int 型数组来存储大数在各个位上的值。例如，数：122333444455555666666，可通过一个足够长的数组 $ary[]$，使 $ary\left[0\right]=1,ary\left[1\right]=2,ary\left[3\right]=2,\dots ,ary\left[20\right]=6$ 进行存储。采取数位与索引大小相对应的存储方式（即数的低位对应较小的索引，高位对应较大的索引），是为了便于大数在执行加法运算时的进位可直接在数组中向后拓展。接下来，就能按照以上思路来扫描数组并对各个位进行加法运算。最后，单独用一层循环处理进位即可。即：

2. 高精度加法运算的例题

【马蹄集】 MT2192 A+B problem

问题描述

计算 $A+B(1\le A,B\le {10}^{10000})$。

格式

输入格式：两行每行一个整数 $A,B$。
输出格式：一个整数 $A+B$。

样例

输入：
1
1

输出：
2

参考代码

/*
    MT2192 A+B problem 
*/
#include<bits/stdc++.h> 
using namespace std;

const int N = 1e4+5;
int numa[N], numb[N];

// 计算两个大数之和（输入为字符串） 
void getSum(string stra, string strb)
{
    
    // 赋初值
    memset(numa, 0, sizeof(numa));
    memset(numb, 0, sizeof(numb));
    int tmp = 0;
    // 将两个字符串保存至 int 型数组中（注意逆序） 
    for(int i=stra.length()-1; i>=0; i--)
        numa[tmp++] = stra[i] - '0';
    tmp = 0;
    for(int i=strb.length()-1; i>=0; i--)
        numb[tmp++] = strb[i] - '0';
    // 将数组中的每个数按位进行加法运算
    for(int i=0;i<N;i++)
        numa[i] += numb[i];
    // 对存放加法结果的数组执行进位处理
    for(int i=0; i<N; i++){
    
        numa[i+1] += numa[i] / 10;
        numa[i] %= 10;
    }
}

// 输出大数加法后的结果 
void printBigData()
{
    
    // 从最高位向后扫描，直到第 1 个非 0 数字出现 
    int p = N-1;
    while(numa[p] == 0) p--;
    while(p >= 0) cout<<numa[p--];
    cout<<"\n";
} 

int main( )
{
    
    // 获取输入 
    string stra, strb;
    cin>>stra>>strb;
    // 对两个大数进行加法运算 
    getSum(stra, strb);
    // 输出和
    printBigData();
    return 0;
} 

---

3、减法运算

1. 高精度减法运算的数理过程

为便于分析，我们先回顾下多位数减法的流程（如下图所示）：

该过程会从数的最低位开始依次往高位进行计算，具体的减数过程为：

• $6<9$，因此会发生借位（则较高位由 $5$ 减为 $4$），于是原位的值为 $6+10-9=7$（其中的 $+10$ 是向较高位借位所得）。
• $4<8$，因此会发生借位（则较高位由 $4$ 减为 $3$），于是原位的值为 $4+10-8=6$（其中的 $+10$ 是向较高位借位所得）。
• $3<7$，因此会发生借位（则较高位由 $3$ 减为 $2$），于是原位的值为 $3+10-7=6$（其中的 $+10$ 是向较高位借位所得）。
• $2>0$，不会发生借位，于是原位的值为 $2-0=2$。
• $2>0$，不会发生借位，于是原位的值为 $2-0=2$。
• $1>0$，不会发生借位，于是原位的值为 $1-0=1$。

所有位均计算完毕，最终得到差为：$122667$。

这便是多位数减法的执行过程，这对具有高精度的大数也适用。同样地，他也需要用到 int 型数组来存储大数在各个位上的值，其存储规则和大数加法一致（即低位对应较小的索引，高位对应较大的索引）。接下来，只需要扫描数组，在每个位上按照以上思路进行减法运算即可得到大数减法的结果。即：

2. 高精度减法运算的例题

【马蹄集】 MT2193 A-B problem

问题描述

计算 $A-B(1\le B\le A\le {10}^{10000})$。

格式

输入格式：两行每行一个整数 $A,B$。
输出格式：一个整数 $A-B$。

样例

输入：
2
1

输出：
1

参考代码

/*
    MT2193 A-B problem 
*/
#include<bits/stdc++.h> 
using namespace std;

const int N = 1e4+5;
int numa[N], numb[N];

// 计算两个大数之差（输入为字符串） 
void getSub(string stra, string strb)
{
    
    // 赋初值
    memset(numa, 0, sizeof(numa));
    memset(numb, 0, sizeof(numb));
    int tmp = 0;
    // 将两个字符串保存至 int 型数组中（注意逆序） 
    for(int i=stra.length()-1; i>=0; i--)
        numa[tmp++] = stra[i] - '0';
    tmp = 0;
    for(int i=strb.length()-1; i>=0; i--)
        numb[tmp++] = strb[i] - '0';
    // 将数组中的每个数按位进行减法运算
    for(int i=0;i<N;i++){
    
        numa[i] -= numb[i];
        if(numa[i] < 0){
    
            // 借位 
            numa[i+1]--; 
            numa[i] += 10;
        }
    }
}

// 输出大数减法后的结果 
void printBigData()
{
    
    // 从最高位向后扫描，直到第 1 个非 0 数字出现 
    int p = N-1;
    while(numa[p] == 0) p--;
    while(p > -1) cout<<numa[p--];
    cout<<"\n";
} 

int main( )
{
    
    // 获取输入 
    string stra, strb;
    cin>>stra>>strb;
    // 对两个大数进行减法运算 
    getSub(stra, strb);
    // 输出和
    printBigData();
    return 0;
} 

---

4、乘法运算

1. 高精度乘法运算的数理过程

我们知道，多位数的乘法实际上可分解为某个数与另一个数在各个位上的乘法之和，如下图所示：

从多位数的乘法过程可以看出，它主要分为 4 步：

• 将乘数中的其中一个数按位分解；
• 对分解后的各数按位乘；
• 对各数位的乘法结果进行进位
• 汇总各数位上的乘法结果。

在实际编码时，我们可用 int 型数组来存储大数在各个位上的值，其存储规则和大数加法一致（即低位对应较小的索引，高位对应较大的索引）。接下来，可通过一个二重循环来对两个大数进行扫描，以实现对两个大数之间的全部数乘运算。这里有一点需要注意：扫描大数的两个索引实际上正指示了当前数乘运算的结果应该存放的位置。即，$numa[i]\times numb[j]=ans[i+j]$。

2. 高精度乘法运算的例题

【蓝桥杯】 算法提高 P1001 大数运算

问题描述

当两个比较大的整数相乘时，可能会出现数据溢出的情形。为避免溢出，可以采用字符串的方法来实现两个大数之间的乘法。具体来说，首先以字符串的形式输入两个整数，每个整数的长度不会超过15位，然后把它们相乘的结果存储在另一个字符串当中（长度不会超过30位），最后把这个字符串打印出来。例如，假设用户输入为：62773417 和 12345678，则输出结果为：774980393241726。

输入样例

62773417 12345678

输出样例

774980393241726

---

参考代码

/*
    【蓝桥杯】 算法提高 P1001 大数运算
*/
#include<bits/stdc++.h> 
using namespace std;

const int N = 16;
const int NN = N*2;
int arya[N], aryb[N], ans[NN];

// 高精度乘法运算
void getProduct(string stra, string strb)
{
    
    // 初始化存放大数的数组 
    memset(arya, 0, sizeof(arya));
    memset(aryb, 0, sizeof(aryb));
    memset(ans, 0, sizeof(ans));
    // 将字符串数字保存进整型数组
    int tmp = 0;
    for(int i=stra.length()-1; i>=0; i--)
        arya[tmp++] = stra[i] - '0';
    tmp = 0;
    for(int i=strb.length()-1; i>=0; i--)
        aryb[tmp++] = strb[i] - '0';
    // 按位进行乘法 
    for(int i=0;i<stra.length();i++)
        for(int j=0;j<strb.length();j++)
            ans[i+j] += arya[i]*aryb[j];
    // 进位处理 
    for(int i=0; i<NN; i++){
    
        ans[i+1] += ans[i]/10;
        ans[i] %= 10;
    }
    
}

// 输出高精度运算后的大数
void printBigData()
{
    
    // 从最高位向后扫描，直到第 1 个非 0 数字出现 
    int p = NN-1;
    while(ans[p] == 0) p--;
    // 输出大数乘法运算的结果 
    while(p > -1) cout<<ans[p--];
    cout<<"\n";
} 

int main()
{
    
    // 获取输入
    string stra, strb;
    cin>>stra>>strb;
    // 执行大数乘法运算 
    getProduct(stra, strb);
    // 输出 
    printBigData();
    return 0;
} 

---

【洛谷】 P1037 产生数

问题描述

两给出一个整数 $n（n<10^{30})$以及 $k$ 个变换规则（$k\le 15$）。
规则：

• 一位数可变换成另一个一位数。
• 规则的右部不能为零。

例如：$n=234$。有规则（$k=2$）:
$2\to 5$
$3\to 6$
上面的整数 234 经过变换后可能产生出的整数为（包括原数）:
234
534
264
564
共 4 种不同的产生数。现在给出一个整数 $n$ 和 $k$ 个规则。求出经过任意次的变换（0 次或多次），能产生出多少个不同整数。仅要求输出个数。

输入格式

第一行两个整数 $n,k$。
接下来 $k$ 行，每行两个整数 $x_i,y_i$ 。

输出格式

输出能生成的数字个数。

输入样例

234 2
2 5
3 6

输出样例

4

资源限制

时间限制：1.0s   内存限制：125.0MB

---

这道题实际上是求在特定变换规则下，一个指定数能有多少种变换。而该变换规则实际上就是规定一个数字能变换为哪些目标数字（$0$ 除外）。就像上面的例子，由于 $2$ 能变换为 $5$（加上它自己本身，那么 $2$ 就有两种变换：$2\to 2$、$2\to 5$），同理 $3$ 也有两种（$3\to 3$、$3\to 6$）；再看这个数字本身，其中含有 $1$ 个 $2$、$1$ 个 $3$，那么不难算出其总的变换共有 $2\times 2=4$ 种。另外，还要注意数字变换中存在的传递关系，例如，对于变换 $1\to 2,1\to 3,2\to 4,2\to 5$，这时候应得到：1 有五种变换规则（ 1 → { 1 , 2 , 3 , 4 , 5 } 1\to \{1, 2, 3, 4, 5\} 1→{ 1,2,3,4,5}），2 有三种变换规则（ 2 → { 2 , 4 , 5 } 2\to \{2, 4, 5\} 2→{ 2,4,5}）。

所以，本题的总体求解思路如下：

1. 根据输入的 $k$ 个变换规则，得到每个数能有多少种变换。；
2. 统计出给出的整数 $n$ 中，每个数字各有多少个，以便于计算最终的变换个数；
3. 本题中 $n$ 的取值范围最大可达 $10^{30}$，这已经超出了 long 的长度，所以必须解决大数运算的问题。

问题 1：求解每个数的可变换数量

由于数字一共有 10 个，因此可以用一个 $10\times 10$ 的二维矩阵来存放数字之间的可达关系，之所以选用邻接矩阵作为存放可达关系的数据结构是因为后续可以通过佛洛伊德算法来将这些间接的可达关系全部转换为直接可达，进而得到每个数的可变换数量（如 $1\to 2$ 且 $2\to 3$，那么就有 $1\to 3$）。

注：佛洛伊德算法是一个利用动态规划的思想来寻找给定的加权图中多源点之间最短路径的算法。因此当对一个带有权值的二维数组进行佛洛伊德算法后，它将得到这个二维数组所反映的图中各点的距离，也就反映了各点之间的可达关系。下面给出通过佛洛伊德算法来将规格为 $10\times 10$ 的二维矩阵 map 中所有间接可达的点变换为直接可达的代码：

void Floyd()
{
      
	for (int k = 0;k < 10;k++)
		for (int i = 0;i < 10;i++)
			for (int j = 0;j < 10;j++) 
				if(map[i][k]&&map[k][j])
					map[i][j]=1;
}

问题 2：如何统计所有的变换个数

实际上统计变换个数很简单，只需要一层循环去遍历 $n$ 中的每个数字，然后依次叠乘每个数字的可变换个数就能得到最终的变换总数。但是这里有个问题，考虑一种极端情况，假如每个数字之间都能相互变换（即每个数都有 10 种变换），那么对于一个长度为 30 的数字，其总的变换个数就为 1030，而这个数已经超过了 long，因此我们必须自己设计一个大数运算的算法，而不是直接用系统定义的数据类型进行乘法运算。

由于本题在进行叠乘时，总是一个不大于 10 的数字乘以之前的数，因此这里的大数相乘可以直接用当前的可变换数依次与前面的大数的每位进行乘法运算，然后再进行进位操作。算法如下：

for (i=0;i<len;i++)						// len 表示当前输入的n的长度
{
    
	for(j=0;j<31;j++)					// 31是设置的最长的扫描距离，大于30即可
		    ans[j] *= change[n[i]-'0'];	// ans是最终的结果数组
	for(int j=0;j<31;j++)
	{
    
		    if(ans[j] > 9) 
		    {
    
				ans[j+1] += ans[j]/10;
				ans[j] %= 10;
		    }
	}
}

下面给出基于以上思路得到的完整代码：

#include<iostream>
#include<cstring>
using namespace std;

int map[10][10];		// 用于弗洛伊德算法求每个数的可变换数量
int change[10];			// 用于统计每个数的可变换个数
int const MAXN = 10;	// 最多可变换的数字
int const MAXL = 31;	// 最终答案的最大长度（大于30即可）

void Floyd()			// 弗洛伊德算法(求解每个数的可变换数量)
{
      
	for (int k = 0;k < MAXN;k++)
		for (int i = 0;i < MAXN;i++)
			for (int j = 0;j < MAXN;j++) 
				if(map[i][k]&&map[k][j]) 
					map[i][j]=1;
}

int main()
{
    
	char n[MAXL];		// 由于输入的数据范围超过了C提供的最长数据类型，因此这里用字符串替代
	int k;				// 变换规则总数
	while(cin>>n>>k)
	{
    
		int i,j=0,x,y;
		for(i=0;i<k;i++)
		{
    
			cin>>x>>y;
			map[x][y]=1;			// 注意这里构建的map是有向的
		} 
		Floyd();					// 求出可达矩阵
		for(i=0;i<MAXN;i++)			// 找出每个数的可变化数量，并将其存进数组change中
        {
    
            map[i][i]=1;			// 注意自己和自己也算是一种可达
            for(j=0;j<MAXN;j++)
                if(map[i][j])
					change[i]++;
        }
		int len=strlen(n);			// 输入的字符串的长度 
		int ans[MAXL]={
    0};			// 用于贮存最后的变化总数（即最终存放结果的数组）
		ans[0]=1;					// 必须将ans[0]初始化为1
		for (i=0;i<len;i++) 		// 遍历输入的 n 以统计所有的变换个数
		{
    
			for(j=0;j<MAXL;j++) 	// 这里的循环结束条件只能是<MAXL，不能是sum[j]!=0，下同 
				ans[j] *= change[n[i]-'0']; 
			for(j=0;j<MAXL;j++)		// 因为有可能中间某个数为0，此时若以sum[j]!=0作为循环结束 
			{
    						// 条件则会提前结束判断从而导致错误
				if(ans[j] > 9) 
				{
    
					ans[j+1] += ans[j]/10;		//进位
					ans[j] %= 10;
				}
}
		}
		i=MAXL-1;					// 重新将指针置于 ans 的最末尾之前（即最高位之前）
		while(!ans[i]) i--;			// 以找到第一个非零最高位
		while(i>-1)	cout<<ans[i--];	// 依次取出并输出
		cout<<endl;
	}
	return 0;
}

---

5、相关练习

趁热打铁：【马蹄集】第二十四周 —— 高精度计算专题

END

---