🔗 UVA-10093 An Easy Problem!

tags: `數學(Math)`

範例程式碼已於 UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

給定一個 $N$ 進位制的整數 $R$ ，你需要找出 $N$ 的最小可能值，使得 $R$ 可以被 $(N-1)$ 整除，如果不存在這樣的 $N$ ，則輸出 "such number is impossible!"。

$N$ 的範圍是 $2$ 到 $62$ ，其中 $62$ 進位制使用 $0$ 到 $9$ 、 $A$ 到 $Z$ 和 $a$ 到 $z$ 作為數字符號， $61$ 進位制使用 $0$ 到 $9$ 和 $A$ 到 $Z$ 以及 $a$ 到 $y$ 作為數字符號，依此類推。

比較古老的翻譯中提到，測資可能是包含非合法字元的，所以要先判斷是不是英文或數字。

LuckyCat 的中文翻譯

思路：數學(Math)

首先以 $10$ 進位為例，在國中小中時我們學過如何判定 $9$ 的倍數，也就是一個數字 $R = a_0 + a_1 \cdot 10 + a_2 \cdot 10^2 + \cdots + a_n \cdot 10^n$ 是否可以被 $9$ 整除，可以用 $\sum a_i$ 是否可以被 $9$ 整除來判定。這個方法可以推廣到其他進位制。

也就是說，一個數字 $R = a_0 + a_1 \cdot N + a_2 \cdot N^2 + \cdots + a_n \cdot N^n$ 可以被 $(N-1)$ 整除，等同 $\sum a_i$ 可以被 $(N-1)$ 的倍數整除，具體證明如下：

首先，對於 $N^k$ $N^{k}$ ，其除以 $(N-1)$ $(N - 1)$ 的餘數為 $1$ $1$ ，由以下推導可知：
- $N^k = (N-1) N^{k-1} + N^{k-1}$ ，因此 $N^k$ 除以 $(N-1)$ 的餘數為等同 $N^{k-1}$ 除以 $(N-1)$ 的餘數，可以遞迴到 $N^0$ 除以 $(N-1)$ 的餘數為 $1$ 為止。
故可以得出 $a_k \cdot N^k$ 除以 $(N-1)$ 的餘數為 $a_k$ 。
因此 $R = a_0 + a_1 \cdot N + a_2 \cdot N^2 + \cdots + a_n \cdot N^n$ 除以 $(N-1)$ 的餘數為 $a_0 + a_1 + a_2 + \cdots + a_n = \sum a_i$ 。
若餘數 $\sum a_i$ 可以被 $(N-1)$ 整除，則 $R$ 可以被 $(N-1)$ 整除。

得出上述結論後，可以先預處理 $s = \sum a_i$ ，再從 $N = \max(a_i) + 1$ 開始遞增地嘗試找到符合條件的最小 $N$ 即可。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 為輸入字串的長度，或是也可以視為數字 $R$ 的位數。
空間複雜度： $\mathcal{O}(n)$ 。

while True:
    try:
        line = input().strip()
    except EOFError:
        break
    A = [] # 逐位轉換成數字
    for ch in line:
        if ch.isdigit(): # [0, 9]
            A.append(int(ch))
        elif ch.isupper(): # [10, 35]
            A.append(ord(ch) - ord("A") + 10)
        elif ch.islower(): # [36, 61]
            A.append(ord(ch) - ord("a") + 36)

    ans = -1
    r = max(A) + 1 # 最小必須為 base-r
    s = sum(A) 
    for i in range(max(2, r), 63):
        if s % (i-1) == 0:
            ans = i
            break
    print(ans if ans != -1 else "such number is impossible!")

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int ans, s, mx;
    string line;
    while (cin >> line) {
        vector<int> A;
        for (char ch : line) {
            if (isdigit(ch)) A.push_back(ch - '0');
            else if (isupper(ch)) A.push_back(ch - 'A' + 10);
            else if (islower(ch)) A.push_back(ch - 'a' + 36);
        }
        s = 0;
        mx = -1;
        for (int x : A){
            mx = max(mx, x);
            s += x;
        }
        ans = -1;
        for (int i = max(2, mx + 1) ; i <= 62; ++i) {
            if (s % (i - 1) == 0) {
                ans = i;
                break;
            }
        }
        cout << (ans == -1 ? "such number is impossible!" : to_string(ans)) << endl;
    }
    return 0;
}