题目链接：点击打开链接
题目大意：给定两个数，其中单个位置上的数值范围可以为 [0-z]。指定其中一个数的进制，试确定是否存在可能的进制让两数的实际值相等。（如果有多个答案，要求最小进制值）
解题思路：
1、input 中两个数字可以是 10 位数，虽然没有告诉 radix 的范围，但在9*10^10 10 1 200这个示例中，可以看到结果的 radix 也可以是很大的。从这个角度看，代码中将 radix 和两个数值都设定为 longlong 是合适的选择。
2、在计算另一个数的 radix 时，简单的遍历 [2, 1018]会超时。单调的区间很自然想到使用二分查找。
3、二分查找的上下界确定能减少耗时：下界选数字的所有位上的最大值+1；上界容易想当然的认为就是题中给定了 radix 的数的值。实际上，示例11 b 1 10就是一个反例，原因在于这个假设忽略了一位数的可能性，解决方案是在取给定 radix 的数值和下界中较大的那个数。
4、二分查找时，不可直接计算出某个 radix 下数的值，因为可能会 longlong 溢出。于是需要用特定的 cmp 函数，在累加的过程中判定是否大于另一个数。算是一种剪枝。
5、当两个数都是 1 时，输出 2。
AC 代码
/
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; string a[3]; ll tag,radix,num; int cal(char c) { if(c>='0' && c<='9') return c-'0'; else return c-'a'+10; } ll Any2D(string s, ll rdx) { ll ans=0, tmp=1; for(int i=s.length()-1;i>=0;i--) { ans+=cal(s[i])*tmp; tmp*=rdx; } return ans; } int cmp(string s,ll rdx) { ll ans=0, tmp=1; for(int i=s.length()-1;i>=0;i--) { ans+=cal(s[i])*tmp; if(ans>num) return 1; tmp*=rdx; } return ans==num?0:-1; } int maxR(string s) { int ans=-1; for(int i=0;i<s.length();i++) ans=max(ans,cal(s[i])); return ans+1; } ll bs(int cur) // 此二分类型是：求最小的i，使得a[i] = key { ll l=maxR(a[cur]), r=max(l,num), m, rs; while(l<r) { m=l+((r-l)>>1); rs=cmp(a[cur],m); if(rs==-1) l=m+1; else r=m; } return cmp(a[cur],r)==0?r:0; } int main() { while(cin>>a[1]>>a[2]>>tag>>radix) { if(a[1]=="1" && a[2]=="1") puts("2"); // else if(a[1]==a[2]) printf("%lld\n",radix); else { num=Any2D(a[tag],radix); int cur=tag==1?2:1, ans=bs(cur); if(ans) printf("%lld\n",ans); else puts("Impossible"); } } return 0; }
