UVa 10093

From Algorithmist
Jump to navigation Jump to search

10093 - An Easy Problem![edit]

Summary[edit]

Given any based number you have to find the minimum base for which that number will be divisible by N-1 in N base.

Explanation[edit]

If this problem is not as easy as its name suggests, then it's not as hard as you may think. You have to find the minimum valid base for that number (maximum digit + 1) and try to divide that number in that base by base-1 to check if divisible until you reach base 62. If it's not divisible by this time then the number is impossible.

The number can be very big to be held in any datatype. So try to divide digit by digit. This problem can be much easier if you know the following formula. Thanks to P.A.Petrov. An N-based number R is divisible by (N-1) if and only if the sum of its digits is divisible by (N-1).

Gotcha's[edit]

No base can be less than 2. There can be negative numbers. Just ignore the sign. Be careful with input "0".

Input[edit]

3
5
A
+A
-A
Z
+Z
-Z
265
5464
    +265
    -5464
11111
AAAAA
ABCD
abcd
XYZ
xyz
123456789
987654321
0
1
2
2727
Zz
1010101101
z
41724
123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
123456789ABCDEFGHIJKLMN

Output[edit]

4
6
11
11
11
36
36
36
14
20
14
20
2
11
24
51
52
such number is impossible!
10
10
2
2
3
10
such number is impossible!
2
62
10
62
24