TIOJ1006-大數除法

題目：http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1006
請將兩個50位數以內的整數數字相除，列印出結果。

程式碼(1)：http://codepad.org/MQQXjzKj
程式碼(2)：http://codepad.org/OTKwhiVh

-------作法(2)
後來想到新的以"code更好寫"為前提設計的算法，效果更好
所以就貼到前面來
有別於(1)那種二分答案，這是基於長除法的
今天要求A/B=C
line39由高到低枚舉商C的位數，最高從被除數A的位數開始
為什麼呢？因為商最大的case就是A/1=A的時候
再來line41就是從9到0枚舉商數C的這個位數應該填多少
每次都模擬填進這個C，然後判斷是否A>=C*B (也就是A.in(C*B))
成功的高位商數都會保留下去

這跟一般長除法有兩點不同：
1.不需要對齊和變換除數的位數
2.已知的商數不需要從被除數中扣除

對人手算來說要扣除比較方便，
但是電腦模擬這一步可說是多餘的、加以省略就是思路清晰的電腦長除法了

-------比較舊的作法(1)
這題有什麼好解題報告的呢？
事實上我AC這題是四個月前的事情
近期又想到一個比長除法容易寫，也就是"編程複雜度"較低的方法
(以下將除法視為正整數除以正整數的除法)

被除數是A、除數是B，那麼設商數P、餘數R
可以得到：A=BP+R (R<B)
其中R<B這一點讓人想起了高一數學和多項式奮鬥的熱血記憶(?)
我們不如換個角度這樣想：
f(x)= (xB<=A) ? 1 : 0
求最大的x滿足f(x)=1
這時候興奮的發現f(x)的值是單調的，x<=P的時候都是1，x>P就都是0
快樂的對f(x)進行二分搜找尋最大的x...

如此一來需要實作的大數功能有：
大數+大數
大數*大數
大數<=大數
大數+1
大數-1
大數/2

二分答案的虛擬碼大致如下
while L<=R do
   M=(L+R)/2
   if f(M)==1 then L=M+1
   else R=M-1
end
return L-1