假定 $d_1$ 與 $d_2$ 內的加減乘除皆能在 $O(1)$ 時間內完成，只要將 ${\log }_{d_2}{d}_1$ 視為常數（以本題而言為 ${\log }_{2}36\approx 5.17$），長度為 $n$ 的大整數 $N$（符號與題目不一致抱歉）的進位制轉換，可以做到 $O(n(\log n{)}^2)$ 的時間複雜度。

設 $N$ 的 $d_1$ 進位表示為 ${a_{n-1}{a}_{n-2}\dots a_0}_{(d_1)}=a_0+a_1{d}_1+\dots +a_{n-1}{d}_1^{n-1}$，其中 $0\le a_i\le d_1-1$，目標找出 $b_0,b_1,b_2,\dots$ 滿足 $0\le b_i\le d_2-1$ 且 $N=b_0+b_1{d}_2+b_2{d}_2^2+\dots$。

不失一般性假定 $n=2^k$（如果 $n$ 不足則補上 leading zeros）。當 $k=0$ 時，我們有 $N=a_0$，直接將 $a_0$ 轉成 $d_2$ 進位，需時 $O({\log }_{d_2}{d}_1)=O(1)$。當 $k\ge 1$ 時，觀察

$$N=(a_0+a_1{d}_1+\dots +a_{2^{k-1}-1}{d}_1^{2^{k-1}-1})+(a_{2^{k-1}}+a_{2^{k-1}+1}{d}_1+\dots +a_{2^k-1}{d}_1^{2^{k-1}-1})d_1^{2^{k-1}}.$$

因此只要分別求出 $N$ 的低位部分 $L(N):={a_{\frac{n}{2}-1}{a}_{\frac{n}{2}-2}\dots a_0}_{(d_1)}$ 、$N$ 的高位部分 $H(N):={a_{n-1}{a}_{n-2}\dots a_{\frac{n}{2}}}_{(d_1)}$、以及上式中的 $d_1^{\frac{n}{2}}$ 的 $d_2$ 進位表示，就能用大數乘法時間複雜度 $O(L\log L)$ 的演算法算出 $N$ 的 $d_2$ 進位表示了，時間複雜度為 $T(n)=2T(\frac{n}{2})+O(n\log n)=O(n(\log n{)}^2)$。

以下雜談：

1. 實際上我的標程都將 $s$ 視為 $N$ 的 $d_1^{w_1}$ 進位表示（一格佔 $s$ 的 $w_1$ 個字元），轉成 $d_2^{w_2}$ 進位後再輸出 $t$。只要確保 $d_1^{w_1}<d_2^{w_2}$，上述介紹的遞迴演算法的 base case 就毋須額外處理。
2. 我後來發現 java 的 BigInteger 以及 python 的內建 int 都提供了 bitwise-and/or/xor 運算。這代表要嘛它們做這些運算的時間複雜度是 $\mathrm{\Omega }(n(\log n{)}^2)$，要嘛它們光 IO 就要 $\mathrm{\Omega }(n(\log n{)}^2)$ 了耶 orz。