UVA-10093: An Easy Problem!

CPE 一顆星選集 49 道必考題

題目連結:https://vjudge.net/problem/UVA-10093

內容

給定一個 N (2 <= N <= 62)進位整數 R (R <= 10^1000)，保證R一定可以用(N-1)除的盡，找出最小的 N。在本問題中，62進位數字系統的符號為（0..9，A..Z，a..z）。類似的，61進位數字系統的符號為（0..9，A..Z，a..y）。依此類推，2進位數字系統的符號為（0..1）。

如果找不到，輸出’such number is impossible!’。

範例輸入

3
+5
-A
4964654623232355454546554546546545464564564565465465454654600655460
-005444554f546554654A5445656466
00000q123
1
0
q12345

範例輸出

4
6
11
62
60
59
2
2
such number is impossible!

想法

如果此數為abc，可以看成
a*N^2 + b*N^1 + c
= a*N*(N-1 + 1) + b*(N-1 + 1) + c
= a*N*(N-1) + a*N*1 + b*(N-1) + b*1 + c
= a*N*(N-1) + a*(N-1 + 1) + b*(N-1) + b + c
= a*N*(N-1) + a*(N-1) + a*1 + b*(N-1) + b + c
= (a*N + a + b)*(N-1) + (a + b + c) #

可以發現，若此數是 (N-1) 的倍數，則 (a + b + c) 必定有一因數 (N-1)，所以只要計算各個位數之和，再去判斷是否有數能使其整除即可。

使用 getline 一次讀取一列，接著依序判斷，若不是62進位數字系統的符號（0..9，A..Z，a..z），直接無視。可用 isdigit(), isupper(), islower()判斷是否為數字、大寫字母、小寫字母。

最後尋找 N-1 時，從各個位數之最大值開始找，像是 48763 就從 8 開始判斷，因為 N <= 8 是不合理的。

若和為 0 直接輸出 2(N的最小值)，避免出現錯誤。

參考資料:YUI HUANG 演算法學習筆記

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;

int main(){
    fastio;
    string s;
    int sum, mxn, temp;
    bool suc;
    while(getline(cin, s)){
        sum = 0, mxn = -50, suc = false;
        for(int i = 0; i < s.length(); ++i){
            if(isdigit(s[i])) temp = s[i]-'0';
            else if(isupper(s[i])) temp = (s[i]-'A')+10;
            else if(islower(s[i])) temp = (s[i]-'a')+36;
            else continue;
            mxn = max(mxn, temp);
            sum += temp;
        }
        if(sum == 0){
            cout << "2\n";
            continue;
        }
        for(int i = mxn; i < 62; ++i){
            if(!(sum%i)){
                cout << i+1 << "\n";
                suc = true;
                break;
            }
        }
        if(!suc) cout << "such number is impossible!\n";
    }
    return 0;
}