# An Easy Problem!(UVA10093)
## [程式繳交區](https://hackmd.io/@Renektonn/SkOUVNydyx/edit)
## 題目
[點我](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1034)

## 演算法

1. 輸入str，若無法，則停止
2. 讓所有字元(數字、英文字母)都能對應一個數字，
2. 比如說，'9'對應到9，'A'對應到10，'B'對應到11
3. 先找出str中最大的字元，再利用2的方法，獲取最小可能的進位制N
3. 並且獲得str中所有數字加總sum
4. for i = N to 62:
4.1  若i - 1整除sum，輸出i
5. 輸出"such number is impossible!"
6. 回到1

## 程式碼

#include <bits/stdc++.h>
using namespace std;

int mapping (char c) {
    int n = -1;
    if ('0' <= c and c <= '9') {
        n = c - '0';
    } else if ('A' <= c and c <= 'Z') {
        n = c - 'A' + 10;
    } else if ('a' <= c and c <= 'z') {
        n = c - 'a' + 36;
    }
    return n;
}

int main() {
    string str;
    while (cin >> str) {
        int idx = 0;
        while (mapping(str[idx]) == -1) {
            idx++;
        }
        int N = 2;
        for (int i = idx; i < str.size(); i++) {
            N = max(N, mapping(str[i]) + 1);
        }
        int sum = 0;
        for (int i = idx; i < str.size(); i++) {
            sum += mapping(str[i]);
        }
        int flag = 1;
        for (int i = N; i <= 62; i++) {
            if (sum % (i - 1) == 0) {
                cout << i << endl;
                flag = 0;
                break;
            }
        }
        if (flag) {
            cout << "such number is impossible!" << endl;
        }
    }

    return 0;
}

## 解題步驟

#### 1. 了解題意
#### 2. 設計演算法
想法:
- 將R轉為10進位，就可以算出最小的N是多少，最後印出答案。

問題:
- 給定R，但不知道R的base是多少，這樣就沒辦法先轉成10進位，再算出N是多少。

想法:
- 為了改善上述問題，窮舉所有可能的base(2~62)，再對照回去。

問題:
- 最差情況是62進位，假設他輸入長度為100，最大的數會到62^100，long long也存不進去

想法:
- 利用數學推導，減少數字範圍

設abc為N進位，則
$$ abc = aN^2 + bN + c $$
$$ = a(N-1)^2 + b(N-1) + 2aN -a + b + c$$
$$ = a(N-1)^2 + b(N-1) + 2a(N-1) + a + b + c$$

- 判斷abc是否被(N-1)整除，等價於判斷a+b+c是否被(N-1)整除
- 最差情況是62進位，假設他輸入長度為100，最大的數會到62*100，int就存得進去了

#### 3. 實際做一次
#### 4. 確定測資範圍
- 由Each line in the input file will contain an integer (as defined in mathematics) number of any integer base (2..62).

所以輸入的數是integer，包含正整數、0、負整數，而且前面可能包含空格
負整數跟空格的問題在第12行有做處理，遇到0則是直接輸出2

- 由於最多到62進位

可能包含字母，所以要用字串存

- 題目沒講字串長度多少

假設字串長度為100，long long也存不進去，才會使用以上的演算法。
#### 5. 檢查輸出格式
a'\n'
b'\n'
c'\n'

## 後記
其實這題蠻難的吧，怎麼只有一顆星

:::warning
輸入都是合法的，除了開頭可能會有+-號以外，其他字元都是，0~9, A~Z, a~z
若直接將輸入的數字轉為十進制，會overflow
:::