No.782 マイナス進数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 62
作問者 : しらっ亭しらっ亭 / テスター : はむこはむこ
2 ProblemId : 1706 / 出題時の順位表

問題文

$T$ 個の非負整数 $N_1, \dots N_T$ を $B$ 進数に変換してください。
ただし、$B$ は、$-10$ 以上 $-2$ 以下の負の整数です。

$B$ 進数$M$ 桁で $a_{M-1} a_{M-2} \dots a_1 a_0$ と表される数は、
$a_{M-1} \times B^{M-1} + a_{M-2} \times B^{M-2} + \dots + a_1 \times B^1 + a_0 \times B^0$ です。
このルールを $B$ が負の整数の場合にも拡張して $B$ 進数に変換してください。

例えば $-3$ 進数 $5$ 桁で $20021$ と表される数は、
$2 \times (-3)^4 + 0 \times (-3)^3 + 0 \times (-3)^2 + 2 \times (-3)^1 + 1 \times (-3)^0$
$= 2 \times 81 + 0 \times (-27) + 0 \times 9 + 2 \times (-3) + 1 \times 1$
$= 162 + 0 + 0 + (-6) + 1$
$= 157$
です。つまり $157$ の $-3$ 進数表現は、$20021$ です。

出力する $B$ 進数表現の先頭には、冗長なゼロを付与してはいけません。
後述のサンプル1の最初の例では、10011だけが正解であり、0100110010011は不正解です。
なお、整数の $B$ 進数表現は、先頭の冗長なゼロを除き一意になることが保障されています。

入力

$T$ $B$
$N_1$
$N_2$
$\vdots$
$N_T$

$T, B, N_1 \dots N_T$ は $10$ 進数表記。
$1 \le T \le 10000$
$-10 \le B \le -2$
$0 \le N_i \le 10^9$
入力は全て整数

出力

$T$ 行に分けて、$N_1$ から $N_T$ を $B$ 進数で表したときの表現を出力してください。

サンプル

サンプル1
入力
5 -2
15
1
5
6
8
出力
10011
1
101
11010
11000

$(-2)^4 + (-2)^1 + (-2)^0 = 16 + (-2) + 1 = 15$
$(-2)^0 = 1$
$(-2)^2 + (-2)^0 = 4 + 1 = 5$
$(-2)^4 + (-2)^3 + (-2)^1 = 16 + (-8) + (-2) = 6$
$(-2)^4 + (-2)^3 = 16 + (-8) = 8$

サンプル2
入力
5 -3
15
1
5
6
8
出力
210
1
122
110
112

$2 \times (-3)^2 + 1 \times (-3)^1 = 18 + (-3) = 15$
$1 \times (-3)^0 = 1$
$1 \times (-3)^2 + 2 \times (-3)^1 + 2 \times (-3)^0 = 9 + (-6) + 2 = 5$
$1 \times (-3)^2 + 1 \times (-3)^1 = 9 + (-3) = 6$
$1 \times (-3)^2 + 1 \times (-3)^1 + 2 \times (-3)^0 = 9 + (-3) + 2 = 8$

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。