当数据的值特别大各种类型都存不下的时候此时就要用高精度算法来计算加减乘除先用字符串读入这个数然后用数组逆序存储该数的每一位利用数组模拟加减乘除运算的过程。高精度算法本质上还是模拟算法用代码模拟小学列竖式计算加减乘除的过程。一、高精度加法P1601 高精度加法题目背景本题是高精度加法的模板题。题目描述给定两个非负整数a,ba,ba,b求它们的和。不用考虑负数。输入格式输入共两行每行一个非负整数分别为a,ba,ba,b。输出格式输出一行一个非负整数表示ababab的值。输入输出样例 #1输入 #11 1输出 #12输入输出样例 #2输入 #21001 9099输出 #210100说明/提示对于20%20\%20%的测试数据a,b≤109a,b \le 10^9a,b≤109对于40%40\%40%的测试数据a,b≤1018a,b \le 10^{18}a,b≤1018对于100%100\%100%的测试数据0≤a,b≤105000\le a,b \le 10^{500}0≤a,b≤10500。解法模拟小学「列竖式」计算「两数相加」的过程。用字符串读入数据将字符串的每一位拆分逆序放在数组中模拟列竖式计算的过程a. 对应位累加b. 处理进位c. 处理余数。处理结果的位数。#includeiostreamusingnamespacestd;constintN1e610;inta[N],b[N],c[N];intla,lb,lc;// 高精度加法的模板 c a bvoidadd(intc[],inta[],intb[]){for(inti0;ilc;i){// 对应位相加, 再加上进位c[i]a[i]b[i];// 处理进位c[i1]c[i]/10;// 处理余数c[i]%10;}if(c[lc])lc;}intmain(){string x,y;cinxy;lax.size(),lby.size(),lcmax(la,lb);// 拆分每一位逆序放在数组中for(inti0;ila;i)a[la-1-i]x[i]-0;for(inti0;ilb;i)b[lb-1-i]y[i]-0;add(c,a,b);for(intilc-1;i0;--i)coutc[i];return0;}二、高精度减法P2142 高精度减法题目描述给定两个正整数a,ba,ba,b求a−ba-ba−b的值。输入格式输入共两行每行一个正整数分别为a,ba,ba,b。输出格式输出一行一个整数表示a−ba-ba−b的值。如果a−b0a-b0a−b0请输出负号。输入输出样例 #1输入 #12 1输出 #11说明/提示对于20%20\%20%的数据a,ba,ba,b在long long类型的存储范围内对于100%100\%100%的数据0a,b≤10100860a,b\le 10^{10086}0a,b≤1010086。解法模拟小学「列竖式」计算「两数相减」的过程。用字符串读入数据判断两个数的大小让较大的数在前。注意字典序 vs 数的大小a. 位数相等按字典序比较b. 位数不等按照字符串的长度比较。将字符串的每一位拆分逆序放在数组中模拟列竖式计算的过程a. 对应位求差b. 处理借位处理前导零。#includeiostreamusingnamespacestd;constintN1e610;inta[N],b[N],c[N];intla,lb,lc;boolcmp(stringx,stringy){// 先比较长度if(x.size()!y.size())returnx.size()y.size();// 再按照字典序的方式比较returnxy;}// 高精度减法的模板 c a - bvoidsub(intc[],inta[],intb[]){for(inti0;ilc;i){// 对应位相减, 然后处理借位c[i]a[i]-b[i];if(c[i]0){c[i1]-1;// 借位c[i]10;}}// 处理前导零while(lc1c[lc-1]0)lc--;}intmain(){string x,y;cinxy;if(cmp(x,y)){swap(x,y);cout-;}lax.size(),lby.size(),lcmax(la,lb);for(inti0;ila;i)a[la-i-1]x[i]-0;for(inti0;ilb;i)b[lb-i-1]y[i]-0;sub(c,a,b);for(intilc-1;i0;--i)coutc[i];return0;}三、高精度乘法P1303 A*B Problem题目背景高精度乘法模板题。题目描述给出两个非负整数求它们的乘积。输入格式输入共两行每行一个非负整数。输出格式输出一个非负整数表示乘积。输入输出样例 #1输入 #11 2输出 #12说明/提示每个非负整数不超过10200010^{2000}102000。解法无进位相乘再相加还是「列竖式」但是每一位相乘的时候不考虑进位直接把乘的结果放在对应位上等到所有对应位置「乘完」并且「累加完」之后「统一处理进位」。#includeiostreamusingnamespacestd;constintN1e610;inta[N],b[N],c[N];intla,lb,lc;// 高精度乘法的模板 c a * bvoidmul(intc[],inta[],intb[]){// 无进位相乘, 然后相加for(inti0;ila;i)for(intj0;jlb;j)c[ij]a[i]*b[j];// 处理进位for(inti0;ilc;i){c[i1]c[i]/10;c[i]%10;}// 处理前导零while(lc1c[lc-1]0)lc--;}intmain(){string s1,s2;cins1s2;las1.size(),lbs2.size(),lclalb;for(inti0;ila;i)a[i]s1[la-i-1]-0;for(inti0;ilb;i)b[i]s2[lb-i-1]-0;mul(c,a,b);for(intilc-1;i0;--i)coutc[i];return0;}四、高精度除法P1480 A/B Problem高精度除法Ⅰ题目描述输入两个整数a,ba,ba,b输出它们的商。输入格式两行第一行是被除数第二行是除数。输出格式一行商的整数部分。输入输出样例 #1输入 #110 2输出 #15说明/提示0≤a≤1050000\le a\le 10^{5000}0≤a≤1050001≤b≤1091\le b\le 10^91≤b≤109。解法模拟小学「列竖式」计算「两数相除」的过程注意我们这里是「高精度 ÷ 低精度」。定义一个指针 i 从「高位」遍历被除数一个变量 t 标记当前「被除的数」记除数是 b更新一个当前被除的数 t t × 10 a[i]t/b 表示这一位的商t%b 表示这一位的余数用 t 记录这一次的余数遍历到下一位的时候重复上面的过程。被除数遍历完毕之后t 里面存的就是余数但是商可能存在前导 0注意清空。#includeiostreamusingnamespacestd;constintN1e610;inta[N],b,c[N];intla,lc;// 高精度除法的模板 c a / b (高精度 / 低精度)voiddiv(intc[],inta[],intb){longlongt0;// 标记每次除完之后的余数for(intila-1;i0;--i){// 计算当前的被除数tt*10a[i];c[i]t/b;t%b;}// 处理前导零while(lc1c[lc-1]0)lc--;}intmain(){string x;cinxb;lax.size();for(inti0;ila;i)a[la-i-1]x[i]-0;lcla;div(c,a,b);for(intilc-1;i0;--i)coutc[i];return0;}
算法学习——高精度加减乘除
当数据的值特别大各种类型都存不下的时候此时就要用高精度算法来计算加减乘除先用字符串读入这个数然后用数组逆序存储该数的每一位利用数组模拟加减乘除运算的过程。高精度算法本质上还是模拟算法用代码模拟小学列竖式计算加减乘除的过程。一、高精度加法P1601 高精度加法题目背景本题是高精度加法的模板题。题目描述给定两个非负整数a,ba,ba,b求它们的和。不用考虑负数。输入格式输入共两行每行一个非负整数分别为a,ba,ba,b。输出格式输出一行一个非负整数表示ababab的值。输入输出样例 #1输入 #11 1输出 #12输入输出样例 #2输入 #21001 9099输出 #210100说明/提示对于20%20\%20%的测试数据a,b≤109a,b \le 10^9a,b≤109对于40%40\%40%的测试数据a,b≤1018a,b \le 10^{18}a,b≤1018对于100%100\%100%的测试数据0≤a,b≤105000\le a,b \le 10^{500}0≤a,b≤10500。解法模拟小学「列竖式」计算「两数相加」的过程。用字符串读入数据将字符串的每一位拆分逆序放在数组中模拟列竖式计算的过程a. 对应位累加b. 处理进位c. 处理余数。处理结果的位数。#includeiostreamusingnamespacestd;constintN1e610;inta[N],b[N],c[N];intla,lb,lc;// 高精度加法的模板 c a bvoidadd(intc[],inta[],intb[]){for(inti0;ilc;i){// 对应位相加, 再加上进位c[i]a[i]b[i];// 处理进位c[i1]c[i]/10;// 处理余数c[i]%10;}if(c[lc])lc;}intmain(){string x,y;cinxy;lax.size(),lby.size(),lcmax(la,lb);// 拆分每一位逆序放在数组中for(inti0;ila;i)a[la-1-i]x[i]-0;for(inti0;ilb;i)b[lb-1-i]y[i]-0;add(c,a,b);for(intilc-1;i0;--i)coutc[i];return0;}二、高精度减法P2142 高精度减法题目描述给定两个正整数a,ba,ba,b求a−ba-ba−b的值。输入格式输入共两行每行一个正整数分别为a,ba,ba,b。输出格式输出一行一个整数表示a−ba-ba−b的值。如果a−b0a-b0a−b0请输出负号。输入输出样例 #1输入 #12 1输出 #11说明/提示对于20%20\%20%的数据a,ba,ba,b在long long类型的存储范围内对于100%100\%100%的数据0a,b≤10100860a,b\le 10^{10086}0a,b≤1010086。解法模拟小学「列竖式」计算「两数相减」的过程。用字符串读入数据判断两个数的大小让较大的数在前。注意字典序 vs 数的大小a. 位数相等按字典序比较b. 位数不等按照字符串的长度比较。将字符串的每一位拆分逆序放在数组中模拟列竖式计算的过程a. 对应位求差b. 处理借位处理前导零。#includeiostreamusingnamespacestd;constintN1e610;inta[N],b[N],c[N];intla,lb,lc;boolcmp(stringx,stringy){// 先比较长度if(x.size()!y.size())returnx.size()y.size();// 再按照字典序的方式比较returnxy;}// 高精度减法的模板 c a - bvoidsub(intc[],inta[],intb[]){for(inti0;ilc;i){// 对应位相减, 然后处理借位c[i]a[i]-b[i];if(c[i]0){c[i1]-1;// 借位c[i]10;}}// 处理前导零while(lc1c[lc-1]0)lc--;}intmain(){string x,y;cinxy;if(cmp(x,y)){swap(x,y);cout-;}lax.size(),lby.size(),lcmax(la,lb);for(inti0;ila;i)a[la-i-1]x[i]-0;for(inti0;ilb;i)b[lb-i-1]y[i]-0;sub(c,a,b);for(intilc-1;i0;--i)coutc[i];return0;}三、高精度乘法P1303 A*B Problem题目背景高精度乘法模板题。题目描述给出两个非负整数求它们的乘积。输入格式输入共两行每行一个非负整数。输出格式输出一个非负整数表示乘积。输入输出样例 #1输入 #11 2输出 #12说明/提示每个非负整数不超过10200010^{2000}102000。解法无进位相乘再相加还是「列竖式」但是每一位相乘的时候不考虑进位直接把乘的结果放在对应位上等到所有对应位置「乘完」并且「累加完」之后「统一处理进位」。#includeiostreamusingnamespacestd;constintN1e610;inta[N],b[N],c[N];intla,lb,lc;// 高精度乘法的模板 c a * bvoidmul(intc[],inta[],intb[]){// 无进位相乘, 然后相加for(inti0;ila;i)for(intj0;jlb;j)c[ij]a[i]*b[j];// 处理进位for(inti0;ilc;i){c[i1]c[i]/10;c[i]%10;}// 处理前导零while(lc1c[lc-1]0)lc--;}intmain(){string s1,s2;cins1s2;las1.size(),lbs2.size(),lclalb;for(inti0;ila;i)a[i]s1[la-i-1]-0;for(inti0;ilb;i)b[i]s2[lb-i-1]-0;mul(c,a,b);for(intilc-1;i0;--i)coutc[i];return0;}四、高精度除法P1480 A/B Problem高精度除法Ⅰ题目描述输入两个整数a,ba,ba,b输出它们的商。输入格式两行第一行是被除数第二行是除数。输出格式一行商的整数部分。输入输出样例 #1输入 #110 2输出 #15说明/提示0≤a≤1050000\le a\le 10^{5000}0≤a≤1050001≤b≤1091\le b\le 10^91≤b≤109。解法模拟小学「列竖式」计算「两数相除」的过程注意我们这里是「高精度 ÷ 低精度」。定义一个指针 i 从「高位」遍历被除数一个变量 t 标记当前「被除的数」记除数是 b更新一个当前被除的数 t t × 10 a[i]t/b 表示这一位的商t%b 表示这一位的余数用 t 记录这一次的余数遍历到下一位的时候重复上面的过程。被除数遍历完毕之后t 里面存的就是余数但是商可能存在前导 0注意清空。#includeiostreamusingnamespacestd;constintN1e610;inta[N],b,c[N];intla,lc;// 高精度除法的模板 c a / b (高精度 / 低精度)voiddiv(intc[],inta[],intb){longlongt0;// 标记每次除完之后的余数for(intila-1;i0;--i){// 计算当前的被除数tt*10a[i];c[i]t/b;t%b;}// 处理前导零while(lc1c[lc-1]0)lc--;}intmain(){string x;cinxb;lax.size();for(inti0;ila;i)a[la-i-1]x[i]-0;lcla;div(c,a,b);for(intilc-1;i0;--i)coutc[i];return0;}
