题目
1010 Radix （25 分）
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 N?1?? and N?2?? , 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 radix
Here 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:
Impossible
思路
题目是给两个数，一个基数，找出另一个基数，使两个数相等。两个数基数不同，难以比大小，故都化为十进制，便于比大小。其中一个易化为十进制数，关键是另一个基数未知。
最简单的思路是进行遍历查找，即遍历每种可能的基数，并比较大小。但题中未给出基数取值范围，只给出了字符取值，显然基数下界有了，那基数的上界如何确定？
题中要求若存在多个基数，取最小的。一个多位数，取不同的基数，还要使数值不变，似乎不可能，除非该数不受基数影响，而一位数的数值是和基数无关的。一个一位数，无论是几进制，都不会改变其数值。那么这个一位数的基数至少是其数值加一。
至此，基数的范围确定下来。
查找的下界似乎可以为2，但最小值设为2，会出现两个测试点结果错误（0和19），而最小值设为最大字符加一时，顺利通过。显然出现了基数小于某个字符的情况。
如果使用遍历，会发现有超时情况，需要对搜索算法进行优化，通过二分查找可以将时间复杂度降低。但还有一个测试点(7)无法通过，是由于该测试点在二分查找中发生溢出导致的。加以判断即可。
#include <stdio.h>
#include <string.h>int to(char a){int r=0;if(a<='9'&&a>='0')r = a-'0';else {r = a -'a'+10;}return r;
}long long int d(char a[],long long d){long long r = 0;int i = 0 ,l = strlen(a);for(i=0;i<l;i++){r = r *d + to(a[i]);}return r;
}int main(){char v[2][11];int tag,sour,aim,i;long long r=0 ,h =0 ,radix;if(4 != scanf("%s %s %d %lld",v[0],v[1],&tag,&radix))return -2;if(tag == 1){sour = 0;aim = 1;}else{sour = 1;aim = 0;}r = d(v[sour],radix);if(r<0)return -2;long long b,e,m;e = r+1;b = 2;if(e<0)e = r;//!!!!for(i=0;i<strlen(v[aim]);i++){if(to(v[aim][i])>=b){b = to(v[aim][i])+1;}}while(b<=e){m = (b+e)/2;h = d(v[aim],m);if(h>r || h<0){ // overstack ,need h<0e = m -1;}else if(h<r){b = m+1 ;}else {printf("%lld",m);return 0;}}printf("Impossible");return 0;
}总结
该题目中大量使用long long int ，而且还会出现long long int 溢出的情况，长见识了，是道好题。
对于long long int ,需要使用lld。
对于char[]，不要忘记\0，开辟空间时需要多一位，即字符串长度加1。