UVA10093

Problem I
An Easy Problem!

Input: Standard Input

Output: Standard Output

Have you heard the fact “The base of every normal number system is 10” ? Of course, I am not talking about number systems like Stern Brockot Number System. This problem has nothing to do with this fact but may have some similarity.  

You will be given an N based integer number R and you are given the guaranty that R is divisible by (N-1). You will have to print the smallest possible value for N. The range for N is 2<=N<=62 and the digit symbols for 62 based number is (0..9 and A..Z and a..z). Similarly, the digit symbols for 61 based number system is (0..9 and A..Z and a..y) and so on.  

Input

Each line in the input file will contain an integer (as defined in mathematics) number of any integer base (2..62). You will have to determine what is the smallest possible base of that number for the given conditions. No invalid number will be given as input.

Output

If number with such condition is not possible output the line “such number is impossible!” For each line of input there will be only a single line of output. The output will always be in decimal number system.

Sample Input

3
5
A

Sample Output

4
6
11






大意:給你一個N進位的整數R，R可以被N-1整除，求最小的N
問題裡面62進制為(0...9, A...Z , a...z) 61進制為(0...9, A...Z, a...y)

Ex:aab2

transform 36 36 37 2
the maximum number = 37
and sum = 36+36+37+2 = 111

111%37=0 so ans = 37 + 1 = 38






import java.util.Scanner;

public class UVA10093 {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);

while (sc.hasNext()) {

String a = sc.nextLine();

long record = 0;
int max = -1;
int answer = -1;

for (int i = 0; i < a.length(); i++) {

record += transform(a.charAt(i));

if (max < transform(a.charAt(i)))
max = transform(a.charAt(i));

}

if (max < 1)
max = 1;

for (int i = max; i <= 61; i++) {

if (record % i == 0) {
answer = i + 1;
break;
}

}

System.out.println(answer == -1 ? "such number is impossible!"
: answer);

}

}

public static int transform(char str) {

if (str >= '0' && str <= '9')
return str - '0';

if (str >= 'A' && str <= 'Z')
return str - 'A' + 10;

if (str >= 'a' && str <= 'z')
return str - 'a' + 36;

return 0;
}


}