PAT A1010 Radix题解

一定要注意
二分搜索时，由于进制上界会可能很大（最大是N1+1），所以转化N2的时候，很有可能超longlong，这时候需要判断是否超范围，并且做相应的判断。

并且，转化过程中使用到的变量，也需要尽量开成longlong

如果bnum（N2转化的数）超了longlong，那就必然是比N1大的，令right=mid-1,向左区间搜索即可。

满分题解，使用二分查找

#include <stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cctype>
#include<string.h>
using namespace std;

const long long inf = (1LL << 63) - 1;
const int maxn=15;
char a[maxn], b[maxn];
long long anum;


//进制转化函数
long long change(char s[], int radix) {
	int len = strlen(s);
	long long res = 0;
	long long mul = 1;//这个变量一定要开成longlong，请思考为什么
	for (int i = len-1; i >=0; i--) {
		char c = s[i];
		int num = 0;
		if (isdigit(c)) {
			num = c - '0';
		}
		else {
			num = 10 + c - 'a';
		}
		res += num * mul;
		if (res < 0)
			return -1;
		mul *= radix;
	}
	return res;
}


//二分求解b的进制
long long binarySearch(char s[], long long left, long long right) {
	long long mid;
	while (left <= right) {
		mid = (left + right) / 2;
		long long bnum = change(s, mid);
		if (bnum < 0) {
			right = mid - 1;
		}
		else if (anum == bnum) {
			return mid;
		}
		else if (bnum > anum) {
			right = mid-1;
			
		}
		else {
			left = mid + 1;
		}
	}
	return -1;
}

int main() {
	//freopen("input.txt", "r", stdin);
	
	int tag, radix;
	scanf("%s %s %d %d", &a, &b,&tag,&radix);

	//radix是a的进制
	if (tag == 2) {
		swap(a, b);
	}
	
	//转化a为10进制
	anum = change(a, radix);

	//求b中最大的数，这样求出b进制的最小可能
	int bmax = 0;
	for (int i = 0; i < strlen(b); i++) {
		int bchar = 0;
		if (isdigit(b[i])) {
			bchar = b[i] - '0';
		}
		else {
			bchar = b[i] - 'a' + 10;
		}
		if (bchar > bmax) {
			bmax = bchar;
		}
	}


	//循环求b进制
	long long i = bmax + 1;

	long long high = max(i, anum)+1;
	long long res=binarySearch(b, i, high);

	if (res==-1) {
		cout << "Impossible";
	}
	else {
		printf("%lld", res);
	}

	return 0;
}

使用暴力搜索（24分），有一个案例超时

#include <stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cctype>
#include<string.h>
using namespace std;

const int maxn=15;
char a[maxn], b[maxn];

//进制转化函数
long long change(char s[], int radix) {
	int len = strlen(s);
	long long res = 0;
	int mul = 1;
	for (int i = len-1; i >=0; i--) {
		char c = s[i];
		int num = 0;
		if (isdigit(c)) {
			num = c - '0';
		}
		else {
			num = 10 + c - 'a';
		}
		res += num * mul;
		mul *= radix;
	}
	return res;
}


int main() {
	//freopen("input.txt", "r", stdin);
	
	int tag, radix;
	scanf("%s %s%d%d", &a, &b,&tag,&radix);

	//radix是a的进制
	if (tag == 2) {
		swap(a, b);
	}
	
	//转化a为10进制
	long long anum = change(a, radix);

	//求b中最大的数，这样求出b进制的最小可能
	int bmax = 0;
	for (int i = 0; i < strlen(b); i++) {
		int bchar = 0;
		if (isdigit(b[i])) {
			bchar = b[i] - '0';
		}
		else {
			bchar = b[i] - 'a' + 10;
		}
		if (bchar > bmax) {
			bmax = bchar;
		}
	}


	//循环求b进制
	long long i = bmax + 1;
	for (i; i <= anum+1; i++) {
		long long bnum = change(b, i);
		if (anum == bnum) {
			break;
		}
	}
	if (i > anum+1) {
		cout << "Impossible";
	}
	else {
		cout << i;
	}

	return 0;
}