无营养内容

……本来想保持月更一篇的，发现这个月没干啥……先放一点水货垫一下吧……
标题的意思是进制转换。（如果有人觉得翻译有问题请联系我= =。）
很久以前叉姐提到过，我表示惊呆，前一段时间和vfk提起，他表示惊呆，一转头说这不是水题吗，我转念一想果然是水题……
当然如果有人会 $O(N \log N)$ 的做法，请告诉我……

问题

给出一个 $A$ 进制数，把它转换为 $B$ 进制。两个进制下的数长度不超过 $10^5$.

题解

把 $A$ 进制数写出来：

$$\sum_{i=0}^{N} a_i*A^i$$

我们只需要在 $B$ 进制下把它求出来即可。
考虑分治：

$$\sum_{i=0}^{N} a_i*A^i = \sum_{i=0}^{\frac{N}{2}-1} a_i*A^i+A^{\frac{N}{2}}*\sum_{i=0}^{\frac{N}{2}} a_{\frac{N}{2}+i}A^i$$

观察到出现了两个递归结构。然后用FFT加速一下就没了。
复杂度：$T(N)=2*T(\frac{N}{2})+O(N \log N)=O(N \log^2 N)$.
果然很水啊……= =。过几天再补一篇理性愉悦的。