PAT 1010 Radix

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

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:

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossibl

数学题一定要考虑溢出的情况

 1 #include<iostream>
 2 #include<string>
 3 #include<cmath>
 4 using namespace std;
 5 /*
 6   烦人的一题， 难点在于数字溢出！
 7   还有就是选取最小的进制， 找出字符串中最大的字母，则最小进制为最大字母代表的数字+1
 8   如果最小进制的值比num的值大，那么最大进制也为最小进制
 9   在进行数的运算的时候 要考虑数字溢出的情况 当整数溢出的时候， 结果会小于0
10   此外进制的上限并非36
11 */
12 long long convert(string s, long long radix){
13   long long ans=0;
14   for(int i=0; i<s.size(); i++){
15     long long temp = (s[i]>='0' && s[i]<='9') ? (s[i]-'0') : (s[i]-'a'+10);
16     ans = ans*radix + temp;
17   }
18   return ans;
19 }
20 const long long inf = pow(2, 62)-1;
21 long long binary(string& s, long long num){
22  char maxx='0';
23  for(int i=0; i<s.size(); i++)
24    if(s[i]>maxx) maxx=s[i];
25  long long low=(maxx<='9' && maxx>='0' ? maxx-'0' : maxx-'a'+10)+ 1, high = low<num? num :low;
26   while(low<=high){
27     long long mid=(low+high)/2, number=convert(s, mid);
28     if(number>num || number<0) high=mid-1;///////////////////////////
29     else if(number<num) low=mid+1;
30     else return mid;
31   }
32   return -1;
33 }
34 int main(){
35   string num1, num2;
36   long long radix, tag, num;
37   cin>>num1>>num2>>tag>>radix;
38   if(tag==1){
39     num = convert(num1, radix);
40     radix=binary(num2, num);
41   }else{
42     num = convert(num2, radix);
43     radix=binary(num1, num);
44   }
45   if(radix==-1) cout<<"Impossible"<<endl;
46   else cout<<radix<<endl;
47   return 0;
48 }