[PAT-A] 1010 Radix

Java

import java.util.Scanner;

public class Main {
    private static final long INF = (long) 1e18;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String n1 = scanner.next();
        String n2 = scanner.next();
        int tag = scanner.nextInt();
        int radix = scanner.nextInt();

        if (tag == 2) {
            String temp = n1;
            n1 = n2;
            n2 = temp;
        }

        long target = calc(n1, radix);

        long l = 0, r = Math.max(target, 36L);
        for (char c : n2.toCharArray()) {
            l = Math.max(l, get(c) + 1);
        }

        while (l < r) {
            long mid = (l + r) >> 1;
            if (calc(n2, mid) >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        if (calc(n2, r) != target) {
            System.out.println("Impossible");
        } else {
            System.out.println(r);
        }
    }

    private static long get(char c) {
        if (c <= '9') {
            return c - '0';
        }
        return c - 'a' + 10;
    }

    private static long calc(String n, long r) {
        long res = 0;
        for (char c : n.toCharArray()) {
            if ((double) res * r + get(c) > 1e16) {
                return INF;
            }
            res = res * r + get(c);
        }
        return res;
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

int get(char c) {
    if (c <= '9') return c - '0';
    return c - 'a' + 10;
}

LL calc(string n, LL r) {
    LL res = 0;
    for (auto c : n) {
        if ((double)res * r + get(c) > 1e16) return 1e18;
        res = res * r + get(c);
    }
    return res;
}

int main() {
    string n1, n2;
    cin >> n1 >> n2;
    int tag, radix;
    cin >> tag >> radix;

    if (tag == 2) swap(n1, n2);
    LL target = calc(n1, radix);

    LL l = 0, r = max(target, 36ll);
    for (auto c : n2) l = max(l, (LL)get(c) + 1);

    while (l < r) {
        LL mid = l + r >> 1;
        if (calc(n2, mid) >= target) r = mid;
        else l = mid + 1;
    }

    if (calc(n2, r) != target) puts("Impossible");
    else cout << r << endl;

    return 0;
}