發表新討論
#54775: C++ 解析


xutingyao0505@gmail.com (TingYao Xu)

n786. 10093 - An Easy Problem! -- UVA | From: [140.117.183.234] | 發表日期: 2026-03-16 10:22

你拿到一個字串 R，你要找出最小的 N。

  1. 找出門檻：先掃一遍字串，找出數值最大的那個字元。假設最大值是 max_v，那麼你的 N 至少要從 max_v + 1 開始嘗試。

    • 特別注意： 題目說 N <= 2，所以如果輸入是 0 或 1，N 最少也要從 2 開始算。

  2. 計算總和：把字串中所有字元的數值加總，得到 sum。

  3. 開始測試：從門檻開始，一個一個往上測到 62。

    • 檢查 sum 是否能被 N - 1 整除？

    • 如果是，這個 N 就是你要的答案！

  4. 失敗處理：如果測到 62 都沒有人能整除，就輸出 such number is impossible!

這題不Easy==
以下為實作程式碼：

#include <bits/stdc++.h>
using namespace std;
 
int charToValue (char c) {
    if (isdigit(c)) return c - '0';
    if (isupper(c)) return c - 'A' + 10;
    if (islower(c)) return c - 'a' + 36;
    return -1;   // 如果輸入為不認識字元回傳-1 但這裡題目不會出現
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    string R;
    while (cin >> R) {
        int max_v = 0;
        long long sum = 0;
        for (char c : R) {
            int value = charToValue(c);
            if (value == -1) continue; // 跳過正負號等非數字字元
           
            if (value > max_v) {
                max_v = value;
            }
            sum += value;
        }
 
        // 最小進位門檻，至少從 2 進位開始
        int start_base = max(2, max_v + 1);
        bool found = false;
 
        for (int i = start_base; i <= 62; ++i) {
            // 數學性質：N 進位的數能被 N-1 整除，則其位數和必能被 N-1 整除
            if (sum % (i - 1) == 0) {
                cout << i << "\n";
                found = true;
                break;
            }
        }
 
        if (!found) {
            cout << "such number is impossible!\n";
        }
    }
    return 0;
}
ZeroJudge Forum