PAT-Advanced Search

Abstract：Binary Search/ DFS/ BFS

1010 Radix (25分)

解法一：二分查找

个人感觉比较难的一题，坑点在于radix并不止于35，比如100zbc，取十位显然可以非常大，需要long long来存

先将一者确定进制的转换为十进制，二分查找另一个数的进制如何转换，如果大了，说明进制取大了，否则小了

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cctype>

std::string n1, n2;
long long tag, radix;

long long toDecimal(std::string& n, long long radix) { // n进制转到十进制
	long long ans = 0, p = 1;
	for (int i = n.length() - 1; i > -1; i--) {
		ans += p * (std::isdigit(n[i]) ? n[i] - '0' : n[i] - 'a' + 10);
		p *= radix;
	}
	return ans;
}

bool generalEquals(std::string& n1, std::string& n2) {
	
	char max = 0;
	for (char& c : n1) max = std::max(c, max);                     // 找到最大的数以确定进制

	long long target = toDecimal(n2, radix),
		lo = (std::isdigit(max) ? max - '0' : max - 'a' + 10) + 1, // char转到long long
		hi = std::max(target, lo),                                 // 最大不超过目标数或lo
		mid;

	while (lo <= hi) {
		mid = (lo + hi) / 2;
		long long decimal = toDecimal(n1, mid);
		if (decimal == target) {
			radix = mid;
			return true;
		}
		else if (decimal < 0 || decimal > target)
			hi = mid - 1;
		else lo = mid + 1;
	}
	return false;
}

int main() {
	std::cin >> n1 >> n2 >> tag >> radix;
	bool e = tag == 1 ? generalEquals(n2, n1) : generalEquals(n1, n2);

	if (e) std::cout << radix;
	else   std::cout << "Impossible";
}