Algorithm‧ICPC‧Programming: PKU 3741 Number System Converter

POJ月賽八月份的題目。

大意是給出一個整數 $N_0$ ，經過 $P$ 進制化轉十進制後變成 $N_1$ ，再轉化成 $Q$ 進利後變成 $N_2$ ，把 $N_2$ 代入 $N_0$ 重覆重作直至 $N_1 - N_2$ 。因為 $Q > P$ ，可以肯定的是若至少經過一遍循環，答案必然在 $P$ 至 $Q-1$ 之間。

不失一般性，先把 $N_0$ 寫成 $Q$ 進制 (注意 $N_0$ 本身可能不是 $Q$ 進制)

$N_0 = \sum_k a_kQ^k$
經過 $P$ 進制化後會變成
$N_1 = \sum_ka_kP^k$
然後得出 $N_0 - N_1 = (Q-P) F(x)$ , 其中 $F(x)$ 是一多項式。
把上式寫成 $N_0 = N_1 + (Q-P)F(x)$
然後可以得出 $N_0 = (Q-P)\sum_kF_k(x) + R$
因此 $R$ 就是最終答案。
可以把題目轉化成 $N_0 \equiv R (Q-P)$ 。
留意的 $R$ 的取值可以在 $[1\dots Q-P-1]$ ，所以要把 $R$ 加上足夠多的 $(Q-P)$ 使其在 $[P\dots Q)$ 。

另外需要留意若輸入的 $N_0$ 根本不會完成一次循環的話， $N_0$ 將會是答案。
因此在特殊情況下 $R$ 可以取值在 $[1..P)$ 。以下的輸入便是一例。
8 10
7

Algorithm‧ICPC‧Programming

2009年9月3日星期四

PKU 3741 Number System Converter

沒有留言:

網誌存檔

關於我自己