DOUBLE - Doubled Numbers
Some numbers have a curious property: when rotating the number to the right, the new number is the double of the original. Rotating the number to the right means choosing the last digit and moving it to the beginning of the number, as the leftmost digit. For example, the number 421052631578947368 when rotated to the right gives 842105263157894736, which is the double of the original. These numbers are expressed in the decimal system. In any numeral system such numbers exist, for example, in the binary (base 2) numeral system, numbers 01 and 0101 have this property. Note that leading zeros are required in this case.
Write a program that, for any given base B (2 <= B <= 250), finds the smallest number in that numeral system which has this property. Try not to precompute the numbers, the solution is very easy and pretty.
Input
The input consists of several test cases. The first line contains an integer T (T <= 20), the number of test cases. The following T lines contain one number B, each.
Output
For each number B, output one or more numbers separated by a blank space that represent the digits in base B (written as decimal numbers) of the smallest number which has this property.
Example
Input: 3 2 10 35 Output: 0 1 0 5 2 6 3 1 5 7 8 9 4 7 3 6 8 4 2 1 11 23
Output explanation
In example #1:
The initial number (when converted to decimal system): 0 * 2^1 + 1 * 2^0 = 1
After applying the rotation: 1 * 2^1 + 0 * 2^0 = 2.
In example #3:
The initial number (when converted to decimal system): 11 * 35^1 + 23 * 35^0 = 408
After applying the rotation: 23 * 35^1 + 11 * 35^0 = 816.
hide comments
akb:
2012-06-12 21:33:30
Nice Question,Good for Learning... |
|
J:
2011-01-29 16:59:37
How to find the unit's digit of the solution number?. If this is done, then the problem can be solved easily. |
|
The Bartender:
2011-01-16 15:18:57
Nice problem!
|
|
Paul Draper:
2009-03-02 08:44:29
0 works. (or 00) |
Added by: | Reinier César Mujica Hdez |
Date: | 2008-11-10 |
Time limit: | 1s |
Source limit: | 3072B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | OCI Olimpiads Cuban in Informatics 2008 day 1 |