1010 Radix （25 point(s)）
Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.
Now for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given.
Input Specification:
Each input file contains one test case. Each case occupies a line which contains 4 positive integers:
N1 N2 tag radixHere N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.
Output Specification:
For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.
Sample Input 1:
6 110 1 10
Sample Output 1:
2
Sample Input 2:
1 ab 1 2
Sample Output 2:
ImpossibleExperiential Summing-up
这一题是得好好说说，就不用英文啦.... 首先，这一题不能用普通的进制转换方法，AC的代码应该也是我学习别人的（去年就提交了，现在也忘了是学习谁的了- -|||），数据的存储方面，读入方式要以字符串读入，在将其转换为整型的数组时，就需要确定这个数的最小进制，就比如，如果数字里最大的是‘ z '，那么它的进制数就不可能小于36。
然后，知道了最小的进制数，还需要知道最大的进制数，设两个数为A和B，其中A已知进制数，那么将其转换为十进制数为Ax，那么最大的进制数为Ax和最小进制数中大的那一个，因为题目说了，如果解不唯一，输出基数最小的那一个。（要知道，题目可没说解的基数在2~36之间哈，基数的上限理论上可以是无穷大，因为题目没有规定）
这一题需要用二分法，否则会有一个测试点超时，这也是题目的又一个坑点，还有，数据的运算与存储都需要用long long型，因为给的数最多为10位，然后如果按35^10小于10^19所以可以用（但是题目确实没有规定基数的范围，可能是题目不严谨吧= =，又或者是我侥幸AC了- -）
还有，二分的时候要注意，当前进制转换为十进制的值sum小于0或者是大于Ax，都是基数过大，因为小于0，按常理来说不应该，但是，有可能是因为数过大溢出导致变成了负数。
暂时能想到的就这么多啦，我理解的也不是十分透彻，毕竟0.11的通过率可是甲级里面倒数第二低的，欢迎大佬评论交流~( •̀∀•́ )
Accepted Code
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
typedef long long LL;
struct bign
{int len;int d[30];bign(){len=0;memset(d,0,sizeof(d));}
};
bign change(char str[],int &q)
{q=1;bign a;a.len=strlen(str);for(int i=a.len-1;i>=0;--i){if(isdigit(str[i])){a.d[a.len-1-i]=str[i]-'0';}else{a.d[a.len-1-i]=str[i]-'a'+10;}q=q>a.d[a.len-1-i]?q:a.d[a.len-1-i];}++q;return a;
}
LL transform(bign a,int r)
{LL ans=0,p=1;for(int i=0;i<a.len;++i){ans+=a.d[i]*p;p*=r;}return ans;
}
int binary_search(LL low,LL high,LL answer,bign a)
{while(low<=high){LL mid=(low+high)/2;LL res=transform(a,mid);if(res==answer)return mid;else if(res>answer||res<0)high=mid-1;elselow=mid+1;}return -1;
}int main()
{int n,tag,radix,r1,r2;char a[20],b[20];scanf("%s %s %d %d",a,b,&tag,&radix);bign a1=change(a,r1);bign b1=change(b,r2);int ans;if(tag==1){LL x=transform(a1,radix);LL l=r2;LL h=max(x,(LL)r2);ans=binary_search(l,h,x,b1);}else{LL x=transform(b1,radix);LL l=r1;LL h=max(x,(LL)r1);ans=binary_search(l,h,x,a1);}if(ans==-1)printf("Impossible\n");elseprintf("%d\n",ans);return 0;
}
