1010 Radix (25 分)

题目

题目链接

题解

二分+数学。

先说几点注意事项：

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 = 0 && res > s1 >> s2 >> tag >> radix;
	if (tag == 2) swap (s1, s2);
	
	LL sum = todecimal (s1, radix);
	
	for (int i = 0;i  1;
		if (check (s2, m, sum)) l = m;
		else r = m - 1;
	}
	
	if (todecimal (s2, l) != sum) puts ("Impossible");
	else cout