10093 - An Easy Problem!

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

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1034

---

這題可能需要知道一個定理會簡單得多，若一個n進位的數可以被n - 1整除，則它每個位數的總和也會被n - 1整除。題目要求找到最小的n，所以我們可以先找到最小的n - 1，這樣就可以找到最小的n。因為n - 1最小要和所有位數裡最大的數相等，所以可以把所有位數裡面最大的數當作找n - 1的起點，接著把61(因為題目說進位最大只到62進位)當作終點，只要一有可以整除所有位數總和的數字出現，它就是最小的n - 1。

c++程式碼:

#include <iostream>
using namespace std;

int main() {
    string input;

    while (cin >> input) {
        int digitSum = 0;
        int ans = -1;
        int maxDigit = -1;

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

            if (input[i] >= 'A' && input[i] <= 'Z')
                thisDigit = input[i] - 'A' + 10;
            else if (input[i] >= 'a' && input[i] <= 'z')
                thisDigit = input[i] - 'a' + 36;
            else if (input[i] >= '0' && input[i] <= '9')
                thisDigit = input[i] - '0';
            else
                continue;
            if (thisDigit > maxDigit)
                maxDigit = thisDigit;
            digitSum += thisDigit;
        }
        if (!maxDigit)
            maxDigit = 1;
        for (int i=maxDigit; i<=61; i++) {
            if (!(digitSum % i)) {
                ans = i + 1;
                break;
            }
        }
        if (ans == -1)
            cout << "such number is impossible!\n";
        else
            cout << ans << endl;
    }

    return 0;
}