P1381. 密码解密

题目描述

石棺本身由一个秘密数字密码锁保护。当有人想要打开它时，必须知道密码并在石棺顶部准确设置。一个非常复杂的机制会打开盖子。如果输入错误的密码，里面的票据会立即着火并永远丢失。密码（由最多100个整数组成）曾被藏在亚历山大图书馆，但不幸的是，如你所知，该图书馆被完全烧毁。

但在18世纪，一位几乎不知名的考古学家获得了密码的副本。他担心密码可能落入"坏人"手中，因此用一种非常特殊的方式编码了这些数字。他随机选取了一个复数$B$，其绝对值大于任何编码数字的绝对值。然后他将这些数字视为以$B$为基数的数字系统中的数字。这意味着数字序列$a_n, a_{n-1}, ..., a_1, a_0$被编码为数字$X = a_0 + a_1B + a_2B^2 + ... + a_nB^n$。

你的目标是解秘密码，即在以$B$为基数的数字系统中表示给定的数字$X$。换句话说，给定数字$X$和$B$，你需要确定"数字"$a_0$到$a_n$。

输入格式

输入包含$T$个测试用例。第一行给出测试用例的数量$T$。每个测试用例由一行组成，包含四个整数$X_r$, $X_i$, $B_r$, $B_i$（$|X_r|,|X_i| \leq 1000000$, $|B_r|,|B_i| \leq 16$）。这些数字表示复数$X$和$B$的实部和虚部，即$X = X_r + i \cdot X_i$, $B = B_r + i \cdot B_i$。$B$是数字系统的基数（$|B| > 1$），$X$是你要表示的数字。

输出格式

对于每个测试用例，你的程序必须输出一行。该行应包含"数字"$a_n, a_{n-1}, ..., a_1, a_0$，用逗号分隔。必须满足以下条件：

• 对于所有$i \in \{0, 1, 2, ..., n\}$：$0 \leq a_i < |B|$
• $X = a_0 + a_1B + a_2B^2 + ... + a_nB^n$
• 如果$n > 0$，则$a_n \neq 0$
• $n \leq 100$

如果没有满足这些条件的数字，输出句子"The code cannot be decrypted."。如果有多个解，输出字典序最小的那个。例如，如果有两组解(4, 3, 18, 9)和(7, 1, 14, 8)，则输出第一组，因为它的字典序更小。

示例输入

4
-935 2475 -11 -15
1 0 -3 -2
93 16 3 2
191 -192 11 -12

示例输出

8,11,18
1
The code cannot be decrypted.
16,15

来源

Central Europe 1999