题目:http://pat.zju.edu.cn/contests/pat-a-practise/1010
题解:
给两个数a,b和a的进制x,问b在哪个进制下和x进制的a相等。
本来看题目只说明了[0-9][a-z]的意义,以为答案最高只有36进制,提交之后错一大片T^T。测试了下,发现要求的进制竟然很大很大,而且可能超过int的表示范围。
如果从最小的进制开始往上枚举测试,最多只有两个测试点过不去。。。
最后的解法只有网上建议的二分搜索。(那么题目中的多种解输出最小进制不是没有意义么?)
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<string> #include<vector> #include<map> #include<set> #include<algorithm> #include<sstream> using namespace std; int charToInt(char x)//字符转数字 { if('0'<=x&&x<='9') return x-'0'; else return x-'a'+10; } long long charToDecimal(char* x,long long radix)//字符串转对应进制数字 { int len=strlen(x); long long ans=0; for(int i=0;i<len;++i) { ans*=radix; ans+=charToInt(x[i]); if(ans<0) return -1; } return ans; } int main() { char as[15],bs[15],temp[15]; long long tag,radix,aimNum; int lenA,lenB; scanf("%s%s%lld%lld",as,bs,&tag,&radix); if(tag==1) { strcpy(temp,as); strcpy(as,bs); strcpy(bs,temp); tag=2; } lenA=strlen(as); lenB=strlen(bs); aimNum=charToDecimal(bs,radix); long long low=2;//进制下限 for(int i=0,j;i<lenA;++i) { j=charToInt(as[i]); if(j>=low) low=j+1; } long long high=aimNum+1;//进制上限 long long aimRadix; long long tempAns; bool flag=false; for(;low<=high;)//二分搜索 { aimRadix=(high+low)/2; tempAns=charToDecimal(as,aimRadix); if(tempAns==-1||tempAns>aimNum) high=aimRadix-1; else if(tempAns<aimNum) low=aimRadix+1; else { flag=true; break; } } if(flag) printf("%lld\n",aimRadix); else printf("Impossible\n"); return 0; }