백준 21275번 폰 호석만

문제 요약

문자열 A, B가 주어진다. 두 문자열이 각각 A진법, B진법으로 표현되어 있다고 했을 때 10진법으로 바꾼 숫자를 A', B'라고 하자.

A' = B' 이면서 A != B인 (A,B)가 정확히 하나 있다면 그 숫자와 A, B를 출력하고 두 개 이상이라면 Multiple, 없다면 Impossible을 출력하자.

이 때, $ 0 \le A', B' \lt 2^{63}$을 만족해야 한다. $ 2 \le A, B \le 36$

주어지는 문자열의 길이는 최대 70이다.

풀이

어떤 문자열을 $B$진법으로 표현되어 있다고 가정하고 10진법으로 변환하는 것은 문자열의 길이만큼 시간이 걸린다.

따라서, 주어진 두 문자열을 2진법부터 시작해서 36진법까지 전부 바꿔 보는 것은 그렇게 시간이 오래 걸리지 않는다.

이제 두 문자열을 가능한 모든 진법에 대해서 시도 해보고 각각 서로 같은 숫자가 있는지 확인하면 된다. 경우의 수는 $35^2$정도이다.

따라서, 진법 변환을 전부 해준뒤 전부 비교해서 문제 조건에 맞게 출력하면 된다.

그러면 진법 변환은 어떻게 할까? 주어진 문자열을 $s$라고 하고 이를 $B$진법으로 표현되었다고 가정하고 $s$를 10진법으로 바꿔보자.

$s_1$부터 시작해서 $s_N$까지 보는데 $s_i$를 숫자로 바꾸자. 0부터 9사이라면 그대로 쓰고 a부터 z라면 10부터 35로 적절하게 바꿔주자.

이 때, 바꾼 숫자가 $B$ 이상이라면 해당 문자열을 $B$진법으로 나타내는 것이 불가능한 것이기 때문에 10진법으로 바꿀 수 없다.

그렇게 해서 최종 숫자가 $x$라면 $x$를 처음에 0으로 초기화하고, 각 $s_i$에 대해서 $x = Bx + s_i$를 해주면 10진법으로 변환이 가능하다. 의사 코드로 나타내면 아래와 같다.

def conv(s, B):
    x <= 0
    for s_i in s:
        if s_i >= B:
            return x <= -1
        x = x*B + s_i
    return x

전체 코드는 아래에 있다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll conv(string s, ll B) {
    ll ret = 0;
    for(char c : s) {
        ll num;
        if('0' <= c &&  c <= '9') num = c - '0';
        else if('a' <= c && c <= 'z') num = c - 'a' + 10;
        if(num >= B) return -1;
        if((LLONG_MAX-num)/B < ret) return -1;
        ret = ret * B + num;
    }
    return ret;
}

int main() {
    string a, b;
    cin >> a >> b;
    vector<ll> A, B;
    for(int i=2;i<=36;++i) {
        A.push_back(conv(a, i));
        B.push_back(conv(b, i));
    }
    int ans = 0;
    ll x = 0;
    int ai, bi;
    for(int i=0;i<A.size();++i) {
        if(A[i] == -1) continue;
        for(int j=0;j<B.size();++j) {
            if(A[i] == B[j] && i != j) {
                ++ans;
                x = A[i];
                ai = i;
                bi = j;
            }
        }
    }
    if(ans == 0) cout << "Impossible" << '\n';
    else if(ans > 1) cout << "Multiple" << '\n';
    else cout << x << ' ' << ai+2 << ' ' << bi+2 << '\n';
    return 0;
}