Problem 1121. -- 高精度除法

1121: 高精度除法

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 241  Solved: 47
[Submit][Status][Web Board]

Description

高精度除法与其它三种高精度运算一样,都是模拟竖式运算过程(高精度乘法可以用快
速傅立叶变换 FFT 优化到 NlogN,这种算法没有模仿竖式运算,暂时忽略) 。在做除法的时
候,依次确定高位到低位上商的每位,最终得到结果。做除法时,有时最高的几位是无法除
的,为了叙述方便,可以看作商的那几位是 0。
概念:被除数:第一个数,分子;除数:第二个数,分母;基:即进制。
我们需要记一个余数(一开始是 0) 。为了获得商的第 i 位,每次将余数乘以基(十进制
就是乘以 10,n 位压缩存储后乘以 10的 n 次) ,然后加上被除数的第 i 位,用得到的结果去
除以除数,得到一个临时商。这个临时商应该是 0 到(基-1)之间的一个数,这个数就是商的
第 i 位。难度在于如何确定这个临时商。
以十进制为例,从大到小枚举临时商,当临时商过大时,临时商与除数的乘积应该会大
于当前的余数。很显然,当乘积第一次小于等于当前余数时,临时商就确定了(因为是从大
到小枚举) 。此时用余数减去这个乘积,就得到新的余数。然后一直从最高位以同样的步骤
做到最低位,最后,余数将被舍弃,商被保留。当然,如果你只保留余数,那就是做高精度
模。还有一种不断的减法:即每次用得到的余数结果减去除数,直到不能减为止,每次减去
后商的第 i 位加 1。很显然这不用做高精乘以低精的乘法,更快更简单。
但是在压缩存储之后,试除法比试减法拥有更高的效率。首先可以看到如果压缩存储,
以 8 位压缩存储为例,试减法在最坏情况下将做将近 10^8 次减法。但是如果做朴素的试除
法,最坏情况也是类似的。我们可以看到,试除时,乘积与临时商是单调递增的正比关系,
于是想到二分法。二分枚举临时商,如果过大,则枚举左区间,否则枚举右区间,直到区间
只剩下一个数为止。总区间应当是[ 0, 基 )。这样,最坏情况下的枚举次数是 log(基) 。
All is done.

Input

两行,两个非负整数,保证第二个数不为 0。

Output

前一个数 div 后一个数的值。

Sample Input

200
3

Sample Output

66

HINT

a,b的长度 <= 10000

Source

[Submit][Status]