©2020-2024 ioDraw All rights reserved,
Privacy Policy
前言
这种类型，在做题过程中多为观察所给数据可能造成的大小来选择是否使用。
属于模板类型，学习者理解其格式并记住大致框架即可熟练应用。
一、什么是大整数（高精度）
想知道什么是大整数，不如换一个解释的方法：什么时候需要用到大整数？
众所周知，int类型的范围是-2147483648~2147483647。long long类型的范围是 -2^63 ~
(2^63)-1。那当题目需要用到或需要输出比long
long类型的范围还要大的数字时，我们是不是就不能用常规办法去接收这些数字了。这个时候使用大整数就可以解决上述问题。即解决接收超出long
long范围数字的问题。
二、大整数的存储
原理很简单，使用数组。
例如定义Int类型数组d[1000]，那么这个数组中的每一位就代表存放整数的每一位。比如将数字123456存储，则有d[0] = 6,d[1] =
5,d[2] = 4,d[3] = 3,d[4] = 2,d[5] = 1。整数的高位存在数组的高位，整数的低位存储在数组的低位。（为了契合加减乘除的思维）
这时候会产生一个需要注意的问题：把整数通过%s或者itoa的方式变成字符串的时候，一开始是逆位存储的，即d[0] = 1...，
因此读入的之后需要在另存为至d[i]数组的时候反转一下。
为了方便随时获取大整数的长度，一般定义len来记录长度，并与d数组组合成结构体。
struct bign{ int d[1000]; int len; };
<>bign是big number的缩写。
一般输入大整数时，都是先用字符串读入，然后再把字符串另存为至bign结构体
。由于使用char数组进行读入时，整数高位会变成数组地位，整数的地位会变成数组的高位。因此为了让整数在bign中是顺位存储，需要让字符串倒着赋值给d[]数组。
bign change(char str[])//将整数转换为bign { bign a; a.len =
strlen(str);//bign的长度就是字符串的长度 for(int i = 0; i < a.len; i++) { a.d[i] =
str[a.len-i-1] - '0'; } return a; }
如果要比较两个bign变量的大小，也很简单：先判断len大小，若不相等，长的为大，若相等，则从高位至低位逐个比较，直到某一位不等，则可以判断两者大小。
int compare(bign a,bign b) { if(a.len > b.len) return 1;//a大 else if(a.len <
b.len) return -1;//a小 else { for(int i = a.len - 1; i >= 0; i--)//从高位到低位开始比较 {
if(a.d[i] > b.d[i]) return 1;//只要有一位a大，则a大 else if(a.d[i] < b.d[i]) return
-1;//只要有一位a小，则a小 } return 0;//两位相等 } }
最后如果需要输出bign变量的值，遍历一遍就可以实现了。
void print(bign a) { for(int i = a.len - 1; i >= 0; i--) {
printf("%d",a.d[i]); } printf("\n"); }
三、大整数的四则运算
1、高精度加法
加法实现方式与我们以前学到的加法一样。对于某一位的运算：我们将该位上的两个数字与进位相加，得到的结果取个位数作为该结果，十位数作为新的进位。
bign add(bign a,bign b) { bign c; int carry = 0; //carry是进位 for(int i = 0; i <
a.len || i < b.len; i++) //以较长的为界限 { int temp = a.d[i] + b.d[i] + carry;
//两个对应位与进位相加 c.d[c.len++] = temp%10; //个位数为该位的结果 carry = temp/10; //十位数为新的进位 }
if(carry != 0) //如果最后进位不为0，则直接赋给结果的最高位 { c.d[c.len++] = carry; } return c; }
这里有一点需要注意，这样写法的条件是两个对象都是非负整数
。如果有一方是负的，可以在转换到数组这一步时去掉符号，再使用高精度减法；如果两个都是负的，都去掉负号后采用高精度加法，最后负号加回去即可。
2、 高精度减法
通过对减法步骤的拆分可以得到一个简练的步骤：对某一位，比较被减位和减位，如果不够减，则令被减位的高位减1，被减位加10再进行减法；如果够减，直接减。最后需要注意减法后高位可能有多余的0，要
去除他们，但也要保证结果至少有一位数。
bign sub(bign a,bign b) //a - b { bign c; for(int i = 0; i < a.len || i <
b.len; i++) //以较长的为界限 { if(a.d[i] < b.d[i]) //不够减 { a.d[i + 1]--; //向高位借位
a.d[i] += 10; //向前位借10 } c.d[c.len++] = a.d[i] - b.d[i]; //减法结果为当前位 }
while(c.len - 1 >= 1 && c.d[c.len - 1] == 0) { c.len--; //去除高位的0，同时至少保留一位最低位 }
return c; }
最后需要指出，使用sub函数前要比较两个数的大小，如果被减数小于减数，需要交换两个变量，然后输出负号，再用sub函数。
3、高精度与低精度的乘法
这里所谓的低精度就是基本数据类型存储的数据，如int。这里就是bign与int的乘法。
对某一位来说是这样的步骤：取bign的某位与int型整体相乘，再与进位相加，所得结果的个位数作为该结果，高位部分作为新的进位。
bign multi(bign a,int b) { bign c; int carry = 0; //进位 for(int i = 0; i <
a.len; i++) { int temp = a.d[i] * b + carry; c.d[c.len++] = temp % 10;
//个位作为该结果 carry = temp / 10; //高位部分作为新的进位 } while(carry != 0)
//和加法不一样，乘法的进位可能不止一位，因此用while { c.d[c.len++] = carry % 10; carry /= 10; }
return c; }
另外，如果a和b中存在负数，需要先记录下负号，然后取他们的绝对值带入函数。
4、高精度与低精度的除法
归纳其中一位的步骤：上一步的余数乘以10加上该步的位，得到该步临时的被除数，将其与除数比较；如果不够除，则该位的商为0；如果够除，则商即为对应的商，余数即为对应的余数。最后一步要注意减法后高位可能有多余的0，要去除他们，但也要保证结果至少有一位数。
bign divide(bign a,int b,int& r) //r为余数 { bign c; c.len =
a.len;//被除数的每一位和商的每一位是一一对应的，因此先令长度相等 for(int i = a.len - 1; i >= 0; i--)
//从高位开始 { r = r * 10 + a.d[i]; //和上一位遗留的余数组合 if(r < b) c.d[i] = 0; //不够除，该位为0
else //够除 { c.d[i] = r / b; //商 r = r % b; //获得新的余数 } } while(c.len - 1 >= 1 &&
c.d[c.len - 1] == 0) { c.len--; //去除高位的0，同时至少保留一位最低位 } return c; }
考虑到很多题目会要求得到余数，因此把余数写成引用的形式直接作为参数传入，或者也可以把余数设成全局变量。