1010 Radix

题目

题目链接

题解

二分+数学。

---

先说几点注意事项：

1. 开 LL；
2. 最高进制不是35，可以更高；
3. 枚举可能的进制时存在爆LL的情况；

---

整体思路：

先计算出知道进制的那个数对应的十进制数，二分进制，找到某个进制使得另一个数对应的十进制数与已知的十进制数相等，如果存在则输出最小进制，如果不存在则输出字符串。

二分的上界并非z对应的进制，而是可以更大，所以上界应该为已知的十进制数（其实我还是不明白如何确定的这个上界）；下界为未知进制的数中出现的最高字符对应的进制+1，再与2取max；

写二分的check函数时，需要注意爆LL的情况，可能会出现未知数的十进制数小于0的情况，出现这种情况的原因是进制取大了；

代码

#include
using namespace std;
typedef long long LL;

LL todecimal (string s, LL r) {
	reverse (s.begin (), s.end ());
	LL res = 0LL;
	for (int i = 0;i < s.size();i ++)
		if (isdigit (s[i])) res += (s[i] - '0') * pow (r, i);
		else res += (s[i] - 'a' + 10) * pow (r, i);
	return res;
}

bool check (string s, LL r, LL sum) {
	LL res = todecimal (s, r);
	return res >= 0 && res <= sum;
}

int main()
{
	string s1, s2;
	int tag;
	LL radix, l = 2LL, r, m;
	
	cin >> s1 >> s2 >> tag >> radix;
	if (tag == 2) swap (s1, s2);
	
	LL sum = todecimal (s1, radix);
	
	for (int i = 0;i < s2.size();i ++)
		l = max (l, LL (isdigit (s2[i]) ? s2[i] - '0' : s2[i] - 'a' + 10) + 1);
	r = max (l, sum);
	
	while (l < r) {
		m = l + r + 1 >> 1;
		if (check (s2, m, sum)) l = m;
		else r = m - 1;
	}
	
	if (todecimal (s2, l) != sum) puts ("Impossible");
	else cout << l << endl;

	return 0;
}