SPOJ Problem Set (classical)
36. Secret Code
Problem code: CODE1

The Sarcophagus itself is locked by a secret numerical code. When somebody
wants to open it, he must know the code and set it exactly on the top of the
Sarcophagus. A very intricate mechanism then opens the cover. If an incorrect
code is entered,
the tickets inside would catch fire immediately and they would
have been lost forever. The code (consisting of up to 100 integers)
was hidden in the Alexandrian Library but unfortunately, as you probably
know, the library burned down completely.
But an almost unknown archaeologist has obtained a copy of the code something
during the 18th century. He
was afraid that the code could get to the ``wrong people'' so he has
encoded the numbers in a very special way. He took a random complex number
B that was greater (in absolute value) than any of the encoded numbers. Then
he counted the numbers as the digits of the system with basis B. That means
the sequence of numbers a_{n},
a_{n1}, ..., a_{1},
a_{0} was encoded as the number
X = a_{0} + a_{1}B + a_{2}B^{2} + ...+
a_{n}B^{n}.
Your goal is to decrypt the secret code, i.e. to express a given number X in
the number system to the base B. In other words, given the
numbers X and Byou are to determine the ``digit''
a_{0} through a_{n}.
Input
The input consists of T test cases (equal to about 100000). The number of them (T) is
given on the first line of the input file. Each test case consists of one single
line containing four integer numbers X_{r},
X_{i}, B_{r}, B_{i}
(X_{r},X_{i} <= 1000000,
B_{r},B_{i} <= 16). These numbers
indicate the real and complex components of numbers X and B,
i.e. X = X_{r} + i.X_{i},
B = B_{r} + i.B_{i}. B is the basis of
the system (B > 1), X is the number you have to
express.
Output
Your program must output a single line for each test case. The line should
contain the ``digits'' a_{n}, a_{n1},
..., a_{1}, a_{0}, separated by
commas. The following conditions must be satisfied:
 for all i in {0, 1, 2, ...n}:
0 <= a_{i} < B

X = a_{0} + a_{1}B + a_{2}B^{2} + ...+
a_{n}B^{n}
 if n > 0 then a_{n} <> 0
 n <= 100
If there are no numbers meeting these criteria, output the sentence
"The code cannot be decrypted.
". If there are more possibilities,
print any of them.
Example
Sample Input
4
935 2475 11 15
1 0 3 2
93 16 3 2
191 192 11 12
Sample output:
8,11,18
1
The code cannot be decrypted.
16,15
Warning: large Input/Output data, be careful with certain languages
Added by:  Adrian Kosowski 
Date:  20040606 
Time limit:  5s

Source limit:  50000B 
Memory limit:  1536MB 
Cluster: 
Cube (Intel Pentium G860 3GHz)

Languages:  All except: SCM chicken 
Resource:  ACM Central European Programming Contest, Prague 1999 