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


2020/8/21 19:35

感想
　　这道题，我感觉有点难，主要是坑点比较多，做了也很长时间，最后看的题解AC的，单靠我自己真做不出来（我是废物）

坑点
　1.进制
　　　刚一开始做题的时候，我以为进制只有0-35，因为题目也说了（0-9，a-z），然而却不是这样。
　　　题目所说的0-9a-z是题目所给的数据。比如测试数据1af8，我们只能确定这个数的进制最低是16(min_radix)，但是却不能确定进制的上限
（比如对于数据‘8’而言，它可能是9进制，也可能是10进制，也可能是1000进制）
　　
　　现在来讨论进制的上限（max_radix）
　　那么现在在题目中，给出了两个数，一个数记为a是已知进制的，另一个记为b未知，假设a=675,为10进制，b=1，未知进制
　　很显然，b的最低进制min_radix是2
　　那么b的最高进制max_radix 是多少呢

　　我们的目的是让a=b，b不可过小也不可过大

　　假设 max_radix=1000
　　很显然b = 1(1000) = 1000 > a = 675
　　所以，发现了吗
　　想让a=b，b的最大进制就是a的值,即675
　　因为我举的例子比较特殊，如果b不为1，那么就很难直接得到b的精确的最高进制max_radix
　　但是 ，可以肯定的是，当b为1 的时候，max_radix是最大的（因为此时b最小）
　　因此，我们虽然不知道b=10,20,80,13671...时，对应的max_radix是多少，但是，他们一定比b=1对应的max_radix小
　　那么我们就可以用最大的max_radix作为进制的上限，在min_radix 到max_radix中二分查找
　　同时需要注意，max_radix>=min_radix

　　　　　　　　　　故有 max_radix = max(a,min_radix);

　　2.查找
　　　　　测试的数据会非常大，挨个遍历是 不现实的
　　　　　观察到，在区间[min_radix,max_radix]上，随着radix的增大，b的值也是逐渐增大，所以整个数列是单调的，可以使用二分查找
　　3.数据类型
　　　一开始用的int类型来保存转换之后的十进制数值，这是非常欠考虑的
　　　　因为随着进制radix的增大（可能达到几百几千进制）一个很短的数就能直接溢出，所以采用longlong类型

　　　　实际上，做题就会发现，即使考虑到以上全部，只能得到15/25的分值，剩下的10分就比较细节
　　　　当我们使用longlong时，其实还是会数据溢出的，溢出之后，变为负数
　　　　
　　　　所以，二分查找时的代码，就需要改动
　　　　当t数据溢出，变成负数，那么我们也需要认为，t>res,否则二分查找的逻辑会混乱。因此加上||t < 0（必须放在二分while循环的第一个if中）

LL BinarySearch(char s[],LL res,LL left,LL right){
    LL flag = 0;
    while(left<=right){

        LL mid = (left+right)/2;
        LL t = toDecimal(s,mid);
        if(t > res || t < 0){//此处的if判断条件非常细节，！！！！！！！！
            //t<0的情况是longlong溢出
            right = mid-1;
        }
        else if(t < res){
            left = mid+1;
        }
        else if(t == res){


            flag = mid;
            right = mid-1;
        }
    }
    return flag;
}

View Code

附上最后的代码

 1 #include <bits/stdc++.h>
 2 
 3 #define LL long long
 4 
 5 using namespace std;
 6 
 7 //把字符类型的0-9a-z转换成整形的函数
 8 int toInteger(char s){
 9     if(s>=‘0‘&&s<=‘9‘){
10             return s-‘0‘;
11         }
12         else if(s>=‘a‘&&s<=‘z‘){
13             return s-87;
14         }
15         return 0;
16 }
17 //把字符串转换成对应的radix进制的函数
18 LL toDecimal(char s[],int radix){
19 
20     int len = strlen(s);
21     LL val=0;//记录结果
22     int exp = 0;//记录次幂
23 
24     for(int i=len-1;i>=0;i--){
25 
26         int number = toInteger(s[i]);
27 
28         val+=number*pow(radix,exp++);
29     }
30 
31     return val;
32 }
33 //在最低进制和最高进制之间二分查找
34 LL BinarySearch(char s[],LL res,LL left,LL right){
35     LL flag = 0;
36     while(left<=right){
37 
38         LL mid = (left+right)/2;
39         LL t = toDecimal(s,mid);
40         if(t > res || t < 0){
41             //t<0的情况是longlong溢出
42             right = mid-1;
43         }
44         else if(t < res){
45             left = mid+1;
46         }
47         else if(t == res){
48 
49 
50             flag = mid;
51             right = mid-1;
52         }
53     }
54     return flag;
55 }
56 int main(){
57     char n[2][20];
58     int tag,radix;
59 
60     cin>>n[0]>>n[1]>>tag>>radix;
61 
62     tag--;
63     int un_tag = 1-tag;
64 
65     //把已知的数转换成十进制
66     LL res = toDecimal(n[tag],radix);
67 
68     //遍历，得到最小的可能成立的 radix（进制）
69     int min_radix = 0;
70     for(int i=0;i<strlen(n[un_tag]);i++){
71         min_radix = max(min_radix,toInteger(n[un_tag][i]));
72     }
73     min_radix++;
74 
75     //得到最大的，radix的上限
76     //max_radix 理解！
77     LL max_radix = max((LL)min_radix,res);
78     //LL max_radix = 6;
79 
80     //-----此处应该二分查找最小的，成立的radix
81     LL flag = BinarySearch(n[un_tag],res,min_radix,max_radix);
82 
83     if(flag != 0){
84         cout<<flag;
85         return 0;
86     }
87     cout<<"Impossible";
88     return 0;
89 
90 
91 }