以下假定$n := \lfloor\log_{10}(\xi)\rfloor+1, m := \lfloor\log_{10}(\eta)\rfloor+1$
計算$\lfloor\xi/\eta\rfloor$ 我們可以用牛頓法做到$O(n(\log n)^2)$的時間複雜度 (參見b960)
牛頓法雖然在$m = n/2$時表現良好
當$m\ll n$時 因為迭代次數大約是$\log_2(n-m)$ naïve演算法(長除法)的$\Theta(m(n-m))$會比牛頓法的$\Theta(n\log(n)\log(n-m))$快
但 不幸地python和java的內建大數都沒有對這種情況做特殊處理
另一方面 似乎很少人討論要怎麼把長除法寫好 網路上一堆亂寫的code
決定出這題卡python/java的內建大數 順便希望大家想想要怎麼把長除法寫好

以下假定$\xi$跟$\eta$都是$A$進位
長除法最麻煩的步驟大概就是猜商的最高位了
或者說 給定一個介於$0$和$A\eta-1$之間的整數$\zeta$ 要怎麼猜$\zeta/\eta$的整數部分
這個也是小學算術中 計算$n$位數除以$m$位數的商 最痛苦的地方
以下各種猜商策略

Stategy 1: 枚舉$0\sim(A-1)$當商的最高位

最無腦的亂寫方法
google了一下 發現一堆code都是採用$A=10$進位 商就$0\sim 9$慢慢試
這樣的計算量大概是$T\times n\times m\times A=3\times 10^{10}$ 顯然沒辦法在5s內跑完

Strategy 2: 令$A=10^k$ 在$0\sim(A-1)$之間二分搜找出商的最高位

這是另一個亂寫方法
計算量大概是$T\times(n/k)\times(m/k)\times(\log_2(10^k))=\frac{\log_2(10)Tnm}{k}$
因為long long只能存$-2^{63}\sim 2^{63}-1$範圍內的整數 $k$最大只能是$9$
這時候計算量大概是$1.11\times 10^9$ 比上一個方法好 可是還是沒辦法在5s內跑完

Strategy 3: 令$A=10^k$ 考慮$x:=(\xi 的最高位), y:=(\eta 的最高位)$ 縮小二分搜範圍

稍微好一點點的亂寫方法
顯然商的最高位只能落在$\lfloor x/(y+1)\rfloor\sim\lfloor x/y\rfloor$之間 可以不用在整個$0\sim(A-1)$之間二分搜
但不幸地當$y=1$時 $\frac{x}{y}-\frac{x}{y+1}=\frac{x}{y(y+1)}=x/2$
如果$x$服從平均分布 請讀者自行驗證這種情況下二分搜次數的期望值大約只會比上一個策略少$2$
所以當$k=9$時 整體的計算量就大概是$T\times(n/9)\times(m/9)\times(\log_2(10^9)-2)=1.03\times10^9$
還是沒有辦法在5s內跑完

Strategy 4: 看最高$1$位不夠 你有看最高$2$位嗎?

喇賽了這麼多 終於要講正解了
剛剛的Strategy 3 怕的是$y=1$ 這會導致$\frac{x}{y(y+1)}$還是太大
注意如果$\eta$只有$1$位 我們根本可以直接算商 不用猜得這麼辛苦
以下假定$\eta$至少有$2$位
如果我們除了看$\eta$的最高位以外 也看$\eta$的次高位 會不會好一點呢
答案是 這樣可以保證商的最高位在$2$次內猜中 不管$A$是多少
改令$x:=(\xi 的最高2位), y:=(\eta 的最高2位)$
一樣我們在$\lfloor x/(y+1)\rfloor\sim\lfloor x/y\rfloor$之間"二分搜"
因為
$$\frac{x}{y} - \frac{x}{y+1} = \frac{x}{y(y+1)} = \frac{\frac{x}{y+1}}{y} < \frac{A}{y} \leq 1$$
範圍內最多只包含了$2$個整數 法喜充滿 殊勝讚嘆
注意我們這邊要求$A^3=10^{3k}$落在long long的範圍裡面 因此$k$最大只能是$6$
這樣整體的計算量就被壓到$T\times(n/6)\times(m/6)\times 2=1.67\times 10^8$ 能在5s內跑完 讚！讚！讚！

這個故事給我們的啟示是
如果我們小時候背的不是$9\times 9$乘法表 而是$99\times 9$乘法表
相信我們在手算除法時 就不會這麼痛苦了XD

大數除法用牛頓法其實可以進一步做到$O(n\log n)$的時間複雜度
不過在這題用牛頓法還是會TLE的@@

真的看不懂題目

以下假定$\xi$跟$\eta$都是$A$進位
長除法最麻煩的步驟大概就是猜商的最高位了
或者說 給定一個介於$0$和$A\eta-1$之間的整數$\zeta$ 要怎麼猜$\zeta/\eta$的整數部分
這個也是小學算術中 計算$n$位數除以$m$位數的商 最痛苦的地方

Strategy 3: 令$A=10^k$ 考慮$x:=(\xi 的最高位), y:=(\eta 的最高位)$ 縮小二分搜範圍

稍微好一點點的亂寫方法
顯然商的最高位只能落在$\lfloor x/(y+1)\rfloor\sim\lfloor x/y\rfloor$之間 可以不用在整個$0\sim(A-1)$之間二分搜
但不幸地當$y=1$時 $\frac{x}{y}-\frac{x}{y+1}=\frac{x}{y(y+1)}=x/2$
如果$x$服從平均分布 請讀者自行驗證這種情況下二分搜次數的期望值大約只會比上一個策略少$2$
所以當$k=9$時 整體的計算量就大概是$T\times(n/9)\times(m/9)\times(\log_2(10^9)-2)=1.03\times10^9$
還是沒有辦法在5s內跑完

其實只要事先對 $\xi$ 和 $\eta$ 分別用線性時間乘上 norm $N(\eta) := \lfloor\frac{A}{y+1}\rfloor$ 得到 $\xi' := N(\eta)\xi$ 與 $\eta' := N(\eta)\eta$，則有 $\lfloor\xi'/\eta'\rfloor = \lfloor\xi/\eta\rfloor$，且猜商範圍內最多只有 $3$ 個整數。

重新定義 $n$ 與 $m$ 為滿足 $A^{n-1}\le\xi<A^n$ 與 $A^{m-1}\le\eta<A^m$ 的正整數。因為 $\eta < (y+1)A^{m-1}$，我們有

\[\eta' = \lfloor\frac{A}{y+1}\rfloor\eta < \frac{A}{y+1}\cdot(y+1)A^{m-1} = A^m,\]

可知 $\eta'$ 在 $A$ 進位下也是 $m$ 位數。另，當 $A$ 為偶數時，觀察 $\eta'$ 的最高位 $y'$ 至少為 $\frac{A}{2}$，可得

\[\frac{x'}{y'}-\frac{x'}{y'+1} = \frac{x'}{y'(y'+1)} < \frac{A}{y'} \le \frac{A}{A/2} = 2,\]

故猜商範圍 $\lfloor\frac{x'}{y'+1}\rfloor$ 至 $\lfloor\frac{x'}{y'}\rfloor$ 最多只有 $3$ 個整數。