请编写一个对大数进行取模运算的程序

计算机最大一般能对64位的数进行加减乘除运算，如果超过这个大小，就无能为力，大数运算的思想就是把数转成数组，对数组进行计算。

算法思路

转换成数组计算，从低到高，一个位一个数，例：123 转成 num=3, num=2, num=1, 再把2个数组相加

charnum1[10] = {3,2,1};//123 低位放低位charnum2[10] = {9,9,9,9,9};//99999cout"123+99999=";for(inti=0; i10; i++){inttmp = num1 + num2;    num1 = tmp%10;//十进制除以10num1[i+1] += tmp/10;}boolbZero =true;for(inti=9; i-1; i--){if(num1[i] !=0)//过滤前面的0bZero =false;if(!bZero)coutint(num1[i]);//需要转成int}coutendl;

最终输出

123+99999=100122

说明：把数组加大就能计算更多的位数，这里位了简化没有考虑溢出的问题，实际上10位数+10位数结果最大可能有11位，后面乘法会给出解决方案

算法思路

依然是转换成数组计算，这里需要用一个技巧，当被减数小于减数时，使用减数-被减数，再取负数的方式进行运算。

//定义一个函数，num1必须大于num2,结果保存在rstvoidmin(char* num1,char* num2,char* rst){//拷贝一份给rst，确保num1不变memcpy(rst, num1,10);for(inti=0; i10; i++)    {if//需要借位{inttmp = rst - num2;            rst = tmp+10;//借位了rst[i+1] -=1;//前一位减1}else{            rst -= num2;         }    }}//比较函数 num1num2 返回1，等于返回0，小于返回-1intcompare(char* num1,char* num2,intn){for(inti = n-1; i-1; i--)    {ifreturn1;ifreturn-1;    }return0;}//main函数charnum1[10] = {3,2,1};//123 低位放低位charnum2[10] = {9,9,9,9,9};//99999charrst[10] = {0};cout"123-99999=";//先判断下num2是否大于num1boolbfushu = compare(num1, num2,10)0;if{    min;cout"-";}else{    min;}//打印结果， bZero用于过滤前面的0boolbZero =true;for(inti=9; i-1; i--){if(rst[i] !=0)//过滤前面的0bZero =false;if(!bZero)coutint(rst[i]);//需要转成int}coutendl;

最终输出

123-99999=-99876

说明：把重复的步骤单独写成函数，可以有效减少代码量

算法思路

依然是转换成数组计算，乘法的技巧是：1234x45678=1234x=1234x40000+1234x5000+1234x600+1234x70+1234x8定义一个函数:void mul_sig_zero比如 mul_sig_zero含义是1234乘5并在后面加3个0，结果保存到rst

//num1乘个位数num2,再在后面加n个0, 结果保存到rst//num1*800 = num1,8,2voidmul_sig_zero(char* num1,charnum2,intn,char* rst){intjinwei =0;inti =0;//num1和num2相乘for(i =0; i10; i++)    {inttmp = num1[i]*num2+jinwei;//相乘rst[i] = tmp%10;        jinwei = tmp/10;    }    rst = jinwei;//最后一位进位//把rst往前移n位for(i = i; i-1; i--)//rst倒叙{        rst = rst;    }//最后把最后n位清0，相当于加n个0for(inti =0; i  n; i++)    {        rst =0;     }}voidmul(char* num1,char* num2,char* rst){boolbzero =true;for(inti =9; i-1; i--)    {//先过滤前面的0ifbzero = num2 ==0;if(!bzero)        {chartmp[20] = {0};//例如第4位是5，就是乘50000mul_sig_zero;//结果累加到rst中，第一小节的加法运算for(inti=0; i20; i++)            {intn = rst + tmp;                rst = n%10;                 rst[i+1] += n/10;            }        }    }}//打印函数 单独写成函数voidprint_num(char* num){boolbzero =true;for(inti =19; i-1; i--)    {if(num[i] !=0)//过滤前面的0bzero =false;if(!bzero)coutint(num[i]);//需要转成int}if(bzero)//全0情况cout0;coutendl;}charnum1[10] = {0,8,8,6,5,4,3,2,1};charnum2[10] = {9,9,9,9,9,0,8,8,0,8};charrst[20] = {0};cout"123456880x8088099999=";mul;print_num(rst);

最终输出

123456880x8088099999=998531591004543120

说明：如果进行一下百度，可以发现还有很多更高效的大数相乘算法，比如Karatsuba法，当然也有更差的办法，123x45就是把123连续相加45次。这里的解法一定是你能想到的"最优"算法,如果你没有学过Karatsuba法,可能花一年时间也想不出来，主要是学解题的思路，最快给出符合题目要求的解才是最好的。

算法思路

既然是除法，不是取模运算，所以我们只要算出商就可以。大数相除的思路跟笔算除法的思路差不多，例如1314563254/23,先把第一位算出来就是131/23=5余165是第八位，把16和剩下的4563254拼一起得 164563254对该数第一位算出来是164/23=7余3，得3563254继续运算直到商为0，最后把各个商放到对应位置拼起来就是结果

这里注意，并不能直接调用内置除法运算，如果除数很大就会溢出所以使用减法来代替除法, 例如131/23就是131连续5次减去23余16

//把num1拆分成2段，前半段是大于num2的最小值，num1必须大于num2//例：传入13579,45， front=135，back=79， 返回2（back数字个数)intsep_num(char* num1,char* num2,char* front,char* back){inti =0;//获取num2的位数for(i =9; i-1; i--)    {if(num2[i] !=0)break;    }    i++;// i=2intj =0;//获取num1的位数for(j =9; j-1; j--)    {if(num1[j] !=0)break;    }    j++;//j=5intr = compare(num1+j-1, num2+i-1, i);if(r0)//同样位数比不过就得多加一位  1345 13545i++;// 3位memcpy;//后三位135给frontmemcpy;//前2位各给backreturnj-i;}//模拟除法运算，实际使用减法 (也可以直接使用该函数)//返回值为商，余数保存在yushu, num1必须大于num2intdiv_sub(char* num1,char* num2,char* yushu){chartmp[10];memcpy(yushu, num1,10);intc =memcmp(num1, num2,10);intshang =0;while(true)    {memcpy(tmp, yushu,10);memset(yushu,0,10);        min;//调用大数相减函数shang++;if(compare(yushu, num2,10)=0)//如果余数num2了就结束break;    }//i就是商，余数是yushureturnshang;}//大数除法运算voiddiv(char* num1,char* num2,char* rst){intn = compare(num1, num2,10);if(n0)//如果num1num2 商为0return;if(n ==0)//相等，商为1{        rst[0] =1;return;    }charfront[10]={0}, back[10]={0};charyushu[10]={0};do{memset(front,0,10);memset(back,0,10);memset(yushu,0,10);intn = sep_num;intshang = div_sub;        rst = (char)shang;//商放在对应的位置//余数往前挪N位chartmp[20] = {0};for(inti =0; i10; i++)            tmp = yushu;//加上back,for(inti =0; i  n; i++)            tmp = back;memcpy(num1, tmp,10);//tmp变成被除数//如果back没有了，或者被除数小于除数了，就结束}while(n0&& compare(num1, num2,10) =0);}intmain(){charnum1[10] = {9,7,1,2,1};charnum2[10] = {0,2};charrst[10] = {0};cout"12179/20=";    div;    print_num(rst,10);return0;}

最终输出

12179/20=608

说明：上面写了一个基于减法的除法运算函数，为什么不直接使用减法做?原因很简单, 如果被除数比较大，除数比较小，用减法会让计算机一直循环只有除数和被除数位数差别不大的时候，才适合用减法至于余数，如果需要，也可以保存出来，并不影响计算难度这里用到的思想其实就是笔算除法的思想