# 10093 - An Easy Problem!

## 題意
給一個 $N$ 進制的數字 $R$，且 $(N-1)|R$，求符合條件的最小 $N$ $(2 \leq N \leq 62)$

由於有可能是 $62$ 進制，因此符號給 $62$ 種: $0$ ~ $9$、$A$ ~ $Z$、$a$ ~ $z$

舉例來說: $A=10$、$B=11$、...\...、$a=36$、$b=37$ 以此類推到 $z$，共 $62$ 種符號

## 推導一些東西
在解這題之前，需要兩個結論

### 引理1

$\forall N, ~ (N-1)|(R_1+R_2+...+R_{N-1}+R_N)$

#### 二位數:
假設一個 $N$ 進位制的二位數 $R$ 表示 $R_1R_2$
$R=R_1 \times N + R_2 = R_1(N-1) + R_1 + R_2$
$\because (N-1)|R$ 且 $R = R_1(N-1) + R_1 + R_2$
$\therefore (N-1)|(R_1+R_2)$
故 $R_1 + R_2$ 也必須可以被 $(N-1)$ 整除

#### 三位數:
假設一個 $N$ 進位制的三位數 $R$ 表示 $R_1R_2R_3$
$\begin{split}
R &= R_1 \times N^2 + R_2 \times N + R_3
\\&= (R_1N(N-1) + R_1N) + (R_2(N-1) + R_2) + R_3
\\&= (R_1N(N-1) + R_1(N-1) + R_1) + (R_2(N-1) + R_2) + R_3
\\&= (R_1N(N-1) + R_1(N-1) + R_2(N-1)) + R_1 + R_2 + R_3
\\&= (R_1N + R_1 + R_2) \times (N-1) + R_1 + R_2 + R_3
\end{split}$
$\because (N-1)|R$ 且 $R = (R_1N + R_1 + R_2) \times (N-1) + R_1 + R_2 + R_3$
$\therefore (N-1)|(R_1 + R_2 + R_3)$
故 $R_1 + R_2 + R_3$ 也必須可以被 $(N-1)$ 整除

#### $K$位數:
假設一個 $N$ 進位制的 $K$ 位數 $R$ 表示 $R_1R_2...R_{K-1}R_K$
$\begin{split}
R &= R_1 \times N^{K-1} + R_2 \times N^{K-2} + ...+R_{K-1} \times N+R_K
\\&= (R_1N^{K-2}(N-1)+R_1N^{K-2})+(R_2N^{K-3}(N-1)+R_2N^{K-3})+...+(R_{K-1}(N-1)+R_{K-1})+R_K
\\&\vdots
\\&=(R_1N^{K-2}+R_2N^{K-3}+...+R_{K-1}+R_K)(N-1)+R_1+R_2+...+R_{K-1}+R_K
\end{split}$$\because (N-1)|R ~且~ R=(R_1N^{K-2}+R_2N^{K-3}+...+R_{K-1}+R_K)(N-1)+R_1+R_2+...+R_{K-1}+R_K$$\therefore (N-1)|(R_1+R_2+...+R_{K-1}+R_K)$
故 $R_1+R_2+...+R_{K-1}+R_K$ 也必須可以被 $(N-1)$ 整除

#### 結論
根據數學歸納法: $\forall N, ~ (N-1)|(R_1+R_2+...+R_{N-1}+R_N)$

### 引理2

一個 $N$ 進位制的 $K$ 位數 $R$ 表示為 $R_1R_2R_3…R_{K-1}R_K$
$R$ 的最小進制至少是 $R_1$ ~ $R_K$ 中最大的數 $+ 1$
例: $3$ 至少是 $4$ 進制 、 $A$ 至少是 $11$ 進制
||這個很 trivial，這裡就不推導了||

## 解題想法

有了兩個結論之後就可以很輕易地設計出算法
對於輸入的數字 $R=R_1R_2...R_N$
1. 把每一位數字加總得到 $sum$
2. 取每一位數字之中的最大值 $max$
3. 從 $max$ 到 $61$ 除除看是否可以整除 $sum$，最小者即為答案
4. 假設從 $max$ 到 $61$ 都沒辦法整除，就輸出 "such number is impossible!\n"