大数除法

示例：

99999999999999999999（20位） / 33333333333333333333（20位） = 3...0

ps: 3...0：表示商为3，余数为0。

思想：这里主要是用大数快速减法来模拟大数除法运算，我们用例子来说明。

先看一简单例子：12 / 3 = 4

化成减法，就是这样。

12 - 3 = 9

9 - 3 = 6

6 - 3 = 3

3 - 3 = 0

这里进行了4次减法运算才使结果小于3，所以商就4.

然后，看一个复杂的例子：12345 / 91 =?135...60

12345 ? ? ? ? ? （由于div1[pos]<div2[0]，此时pos=0，所以++pos，91从div1第二位开始匹配）

? 91 ? ? ? ? ? ? ? ?（进行一次运算，相当于进行了100次减91运算，所以商要加上100。）

----------- ? ? ? ? ?ps:由于开辟了一个长度为len1的数组sum[5]储存商。万sum[0]千sum[1]百sum[2]十sum[3]个sum[4] ?。

03245 ? ? ? ? ? ??所以，如果要加上100，则进行++sum[2]操作。

? ? 91 ? ? ? ? ? ? ?

-----------

02335

? ? 91

-----------

01425

? ? 91

-----------

00515 ? ? ? ? ??我们用zero标记div1高位上最后一个无效0的位置，比如此时zero = 1。

? ? ? 91

-----------

00424 ? ? ? ? ? ??我们用pos标记div2与div1首位匹配的位置，比如此时pos = 3。

? ? ? 91

-----------

00333

? ? ? 91

-----------

00242

? ? ? 91

-----------

00151

? ? ? 91

-----------

00060 ? ? ? ?（此时得到的60小于90，减法结束，同时余数就是60）

/*
	Title:大数除法
	Author:Dojking
*/
#include <iostream>
#include <string>
#include <math.h>
using namespace std;

void BigDiv(string div1,string div2)
{
	int i,j,pos = 0,zero = -1,len1,len2;

	len1 = div1.size()-1;
	len2 = div2.size()-1;
	int *sum = new int[len1+2];      /*开辟空间*/
	for (i = 0; i <= len1+1; ++i)    /*初始化为0*/
		sum[i] = 0;
	while ((&div1[zero+1] >= div2 && len1-zero-1 == len2) || (len1-zero-1 > len2))/*直到被除数小于除数*/
	{
		pos = zero+1;                /*zero表示div1高位最后一个无效0的位置*/
		if (div1[pos] < div2[0])     /*高位匹配位置*/
			++pos;
		for (i = len2+pos,j = len2; j >= 0; --i,--j)/*大数相减*/
		{
			if (div1[i] < div2[j] || div1[i] == 'f')  /*需要借位：在字符串中f表示-1*/
			{
				if (div1[i-1] != 0)    /*上一位可以借位*/
					div1[i-1] -= 1;
				else                   /*上一位为0*/
					div1[i-1] -= 'f';
				if (div1[i] == 'f')    /*运算：本位为f*/
					div1[i] = (-1) + 10 - (div2[j]-'0') + '0';/*将f用-1代替*/
				else
					div1[i] = (div1[i]-'0') + 10 - (div2[j]-'0') + '0';/*借位：即+10*/
			}
			else
			{
				div1[i] = (div1[i]-'0') - (div2[j]-'0') + '0';/*不需借位：直接运算*/
			}
		}
		while (div1[zero+1] == '0' && (zero+1 < len1))/*找到div1高位最后一个无效0的位置*/
			++zero;
		++sum[len2+pos];/*统计结果：做减法的次数就是商*/ 
	}
	for (i = 0; i <= len1; ++i)/*进位*/
	{
		if (sum[i] >= 10)
		{
			sum[i-1] = sum[i]/10;
			sum[i] %= 10;
		}
	}
	i = 0;
	while ((sum[i] == 0) && (i < len1))/*舍掉高位无效0，防止全部为0情况bug*/
		++i;
	for ( ; i <= len1; ++i)    /*输出商*/
		cout<<sum[i];
	cout<<"..."<<&div1[zero+1]<<endl;/*输出余数*/
}

int main()
{
	string div1,div2;

	cin>>div1>>div2;
	BigDiv(div1,div2); /*大数除法*/

	return 0;
}