【PAT(Advanced Level) Practice】1010 Radix（二分）

链接：

https://pintia.cn/problem-sets/994805342720868352/problems/994805507225665536

题意：

有两个数 N 1 ， N 2 N1，N2 N1，N2，已知其中一个数的基数 r a d i x radix radix，问若要使 N 1 = = N 2 N1 == N2 N1==N2，那么另一个数的基数是多少。

思路：

假设：已知 N 1 N1 N1 的基数

我刚开始的思路是将 N 1 N1 N1 先转成 10 10 10 进制，然后再找到 N 2 N2 N2 中每位的数字中最大的那个数 r r r（因为 N 2 N2 N2 的进制一定 ≥ r + 1 \ge r+1 ≥r+1），然后从 r + 1 r+1 r+1 开始并且每步 + 1 +1 +1 顺序去找 N 2 N2 N2 的进制（因为当数 N 2 N2 N2 给定时，它的进制越大， N 2 N2 N2 实际上就越大），对于每一个 r r r 比较在当前 r r r 进制下 N 2 10 进 制 N2_{10进制} N210进制​ 是否 = = = N 1 10 进 制 N1_{10进制} N110进制​，如果 = = = 就找到了，直接输出。如果 N 2 10 进 制 > N 1 10 进 制 N2_{10进制} > N1_{10进制} N210进制​>N110进制​ 则说明等式不可能成立，输出Impossible。（注释掉的代码）

这样做最后有一个测试点超时，我第一反应加上了快速幂，依旧超时。我测试了几次后发现是找 N 2 N2 N2 进制的 while 循环超时了，但是我没想到二分，直到百度之后，我才知道要用二分大法（被自己蠢哭了）。

正解： 上述思路不变，将找 N 2 N2 N2 的进制数 从 顺序查找 优化成 二分查找。二分的下界就是 r + 1 r+1 r+1， 上界设成 N 1 N1 N1（ N 2 N2 N2 的基数 不可能大于已给 N 1 N1 N1，因为 如果 N 2 N2 N2 的基数 > N 1 > N1 >N1，那么只要 N 2 N2 N2 不是 0 0 0， N 2 N2 N2 就一定会大于 N 1 N1 N1，显然不合理）。
但是这样又出现了一个问题： 当 N 2 N2 N2 比较大，在二分尝试比较大的基数的时候，会超 long long 的范围，产生溢出，使得判断条件不成立。（这也是百度知道的，当时已经不动脑了！！！）
解决溢出： 首先可以确定给出的已知数据 N 1 , N 2 N1,N2 N1,N2 最多 10 10 10 位数字，每位最大是 z z z，它们是不会溢出的。那么如果溢出（出现负值），就一定是基数上溢，基数取得过大了。因此多加一个判断即可（N2_10 < 0 || N2_10 > N1_10）。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL qpow(LL x, LL n) {
	LL res = 1;
	while(n) {
		if(n&1) res *= x;
		x *= x;
		n >>= 1;
	}
	return res;
}

LL n2ten(string s, LL radix) {
	// cout<<"s : "<<s<<endl;
	LL res = 0;
	for (int i = s.size()-1; i >= 0; --i) {
		char now = s[i];
		char tmp = (now >= '0' && now <= '9')?'0':'a'-10;
		// cout<<"now-tmp : "<<now-tmp<<endl;
		// cout<<"pow(radix, s.size()-1-i) : "<<pow(radix, s.size()-1-i)<<endl;
		res += (now-tmp)*qpow(radix, s.size()-1-i);
	}
	return res;
}

void solve(string N1, string N2, LL radix) {
	LL N1_10 = n2ten(N1, radix);
	// cout<<"N1_10 : "<<N1_10<<endl;
	char maxE = *max_element(N2.begin(), N2.end());
	char tmp = (maxE >= '0' && maxE <= '9')?'0':'a'-10;
	LL r = maxE - tmp + 1;
	// cout<<"r : "<<r<<endl;
	// while(1) { // TLE
	// 	LL N2_10 = n2ten(N2, r);
	// 	// cout<<"N2_10 : "<<N2_10<<endl;
	// 	if(N2_10 > N1_10) {
	// 		cout<<"Impossible"<<endl;
	// 		return ;
	// 	}
	// 	if(N2_10 == N1_10) {
	// 		cout<<r<<endl;
	// 		return ;
	// 	}
	// 	r++;
	// }
	LL s = r, t = max(s, N1_10); 
	// N2 的基数 不可能大于已给 N1，因为 如果 N2 的基数 > N1，那么只要 N2 不是 0，N2 就一定大于 N1，显然不合理
	while(s <= t) {
		LL m = (s+t) >> 1;
		LL N2_10 = n2ten(N2, m);
		if(N2_10 == N1_10) {
			cout<<m<<endl;
			return ;
		}
		if(N2_10 < 0 || N2_10 > N1_10) t = m-1; 
		// 溢出，给出的已知数据(N1,N2)是不会溢出的，那么只要是取值为负的，全部是上溢，基数取得过大了。
		else s = m+1;
	}
	cout<<"Impossible"<<endl;
}

int main(int argc, char const *argv[])
{
	string N1, N2;
	LL tag, radix;
	cin>>N1>>N2>>tag>>radix;
	if(tag == 2) {
		swap(N1, N2);
	}
	solve(N1, N2, radix);
	return 0;
}

参考链接

1. 1010. Radix (25)-PAT甲级真题（二分法）
2. 1010 Radix (25)（25 分）