UVa11952 - Arithmetic(Math theorm)

題目大意

給你 \(A + B = C \)，請你告訴我這是幾進制的，如果他並不符合進位規則，就輸出 0。
其中 A、B、C 只會是數字，不會有 A、B、C 這些東西

題目連結

重點觀念

• 理解題目的上限

分析

• A、B、C 只會是數字，因此任兩數字相加最高只會是 18
• 當 \(9+9 = 11\)，此時進制是 17。
• 因此我們可以理解，最多只會有 17 進制，此時我們就用一個迴圈直接讓 A、B、C 轉化成其進制，並判斷是否相同即可。
• 當要特判 1，由於 1 進制的 \(10^5\)，會有 \(10^5\) 個數字，long long 塞不下，因此我們這邊要特判，對 1 使用字串檢查

參考連結

UVA 11952: Arithmetic -Solution by codercard

心得

好題，讓我學會理解題目上限的重要性

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
using namespace std;
const int MAXN = 1e5+20;
int t;
string A, B, C, sa, sb;

int base1(){ //判斷是否為 1 進制
    for(int i = 0; i < A.length(); i++){
        if(A[i] != '1') return 0;
    }
    for(int i = 0; i < B.length(); i++){
        if(B[i] != '1') return 0;
    }
    for(int i = 0; i < C.length(); i++){
        if(C[i] != '1') return 0;
    }

    if(A.length() + B.length() == C.length()) return 1;
    return 0;
}

int base(int x){ //判斷是否為 x 進制
    int a = 0, b = 0, c = 0, cnt = 1;
    for(int i = A.length()-1; i >= 0; i--){
        if(A[i] - '0' >= x ) return 0;
        a += (A[i] - '0') * cnt;
        cnt *= x;
    }
    cnt = 1;
    for(int i = B.length()-1; i >= 0; i--){
        if(B[i] - '0' >= x ) return 0;
        b += (B[i] - '0') * cnt;
        cnt *= x;
    }
    cnt = 1;
    for(int i = C.length()-1; i >= 0; i--){
        if(C[i] - '0' >= x ) return 0;
        c += (C[i] - '0') * cnt;
        cnt *= x;
    }
    if(a + b == c) return 1;
    return 0;
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> A >> sa >> B >> sb >> C;
        if(base1() == 1){
            cout << "1\n";
            continue;
        }
        int flag = 0;
        for(int i = 2; i <= 20; i++){ 
            flag = base(i);
            if(flag == 1){
                cout << i << "\n";
                break;
            }
        }
        if(flag == 0) cout << "0\n";
    }
    return 0;
}