1036数的进制转换
正解$O(nlog_{nxt}n)$
这题肯定要高精度的。不会高精度的自己学。
许多同学说,这道题可以先把数化成10进制,再转化成各种进制。其实我们可以用一种快速的解法来求解。
众所周知,在进制转化过程中,我们一次次的除以目标进制,将余数倒着输出,就是答案。比如7转化为三进制:
$7/3=2......1$
$2/3=0......2$
所以7的三进制是$(21)_3$。
同理,我们将$base$进制转化成$nxt$进制时,也要进行这种除法和取余。
一下就是计算高精度除以低精度的方法:
对于高精度的$base=3$进制的数$num=1202$除以$nxt=5$:
$ans$ | 0 | 0 | 0 | 0 |
---|---|---|---|---|
位数 | $num_1$ | $num_2$ | $num_3$ | $num_4$ |
数字 | 2 | 0 | 2 | 1 |
设计低精度余数$rom=0$,高精度商$pre=0$,指针从第四位移动到第一位。
当指针位于第四位时,$rom=rom*base+num_4=1$。
让$ans_4=rom/nxt=0$,$rom=rom~mod~nxt=1$
$ans$ | 0 | 0 | 0 | 0 |
---|---|---|---|---|
位数 | $num_1$ | $num_2$ | $num_3$ | $num_4$ |
数字 | 2 | 0 | 2 | 1 |
当指针位于第三位时,$rom=rom*base+num_3=5$。
让$ans_3=rom/nxt=1$,$rom=rom~mod~nxt=0$
$ans$ | 0 | 0 | 1 | 0 |
---|---|---|---|---|
位数 | $num_1$ | $num_2$ | $num_3$ | $num_4$ |
数字 | 2 | 0 | 2 | 1 |
当指针位于第二位时,$rom=rom*base+num_2=0$。
让$ans_2=rom/nxt=0$,$rom=rom~mod~nxt=0$
$ans$ | 0 | 0 | 1 | 0 |
---|---|---|---|---|
位数 | $num_1$ | $num_2$ | $num_3$ | $num_4$ |
数字 | 2 | 0 | 2 | 1 |
当指针位于第一位时,$rom=rom*base+num_3=2$。
让$ans_3=rom/nxt=0$,$rom=rom~mod~nxt=2$
$ans$ | 0 | 0 | 1 | 0 |
---|---|---|---|---|
位数 | $num_1$ | $num_2$ | $num_3$ | $num_4$ |
数字 | 2 | 0 | 2 | 1 |
所以$(1202)_3~/~5~=~(100)_3......2$
剩下的$(100)_3$可以继续计算。
通过这个例子,相信大家都清楚如何计算高精度除以低精度了吧。自己去切题吧!
讲解人:方彦哲
Fesdrer
感谢观看!!!