pat甲級1010 Radix(二分検索)

1299 ワード

问题を作る+コードを见る2 h...デバグ30分
#include 
#include 
#include 
#include 
#include
using namespace std;
long long convert(string n, long long radix) {
	long long _n = 0;
	int temp=0, index = 0;
	for (auto c = n.rbegin(); c != n.rend(); c++) {
		temp = isdigit(*c) ? *c - '0' : *c - 'a' + 10;
		_n +=temp* pow( radix,index++);
	}
	return _n;
}
long long find_radix(string n,long long num) {
	char it = *max_element(n.begin(), n.end());
	long long low = (isdigit(it) ? it - '0': it - 'a' + 10) + 1;
	long long high = max(num, low);
	while (low <= high) {
		long long mid = (low + high) / 2;
		long long t = convert(n, mid);
		if (t<0||t > num)	high = mid - 1;
		else if (t == num)	return mid;
		else  low = mid + 1;
	}
	return -1;
}
int main() {
	string n1, n2;
	long long tag=0, radix=0, result_radix=0;
	cin >> n1 >> n2 >> tag >> radix;
	if (tag == 1)
		result_radix = find_radix(n2, convert(n1, radix));
	else
		result_radix = find_radix(n1, convert(n2, radix));
	if (result_radix != -1)
		cout << result_radix << endl;
	else
		cout << "Impossible
"; return 0; system("pause"); }