1010 Radix （25 分）

2022-10-22 10:22:55

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 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 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:

Impossible

题意：如果tag=1，则N1是radix进制数，若tag=2，则N2是radix数，问是否存在某进制数使得N2（N1）为N1（N2）的进制数。

分析：因为进制数越大所得到的值越大，比如110，若是二进制，值为6，若为10进制，值为110。

依据这点二分：

1、首先看N1、N2谁大，若N2大交换下N1、N2顺序。2、二分下界为所出现数字中最大数字+1，上界为所给的radix，夹出对应进制数

 /**
 * Copyright(c)
 * All rights reserved.
 * Author : Mered1th
 * Date : 2019-02-26-14.28.46
 * Description : A1010
 */
 #include<cstdio>
 #include<cstring>
 #include<iostream>
 #include<cmath>
 #include<algorithm>
 #include<string>
 #include<unordered_set>
 #include<map>
 #include<vector>
 #include<set>
 using namespace std;

 long long convert(string a,long long radix){ //转化为十进制
     ;
     ,len=a.size();
     ;i<len;i++){
         temp=isdigit(a[i])? a[i]-;
         sum=sum*radix+temp;
     }
     return sum;
 }

 long long find_radix(string a,long long num){
     //二分法，进制数越大数值越大。先确定上下界：下界是最大值+1，比如987，最起码是一个10进制数。而上界是max(下界，N1的十进制）+1；
     char it=*max_element(a.begin(),a.begin());
     )+;
     long long high=max(low,num);
     while(low<=high){
         ;
         long long t=convert(a,mid);
         ||t>num) high=mid-;
         else if(t==num) return mid;
         ;
     }
     ;
 }

 int main(){
 #ifdef ONLINE_JUDGE
 #else
     freopen("1.txt", "r", stdin);
 #endif
     string N1,N2;
     int tag;
     long long radix,ans;
     cin>>N1>>N2>>tag>>radix;
     ){
         swap(N1,N2);
     }
     ans=find_radix(N2,convert(N1,radix));
     ) {
         printf("%lld",ans);
     }else{
         printf("Impossible");
     }

     ;
 }

码农公寓