一、题目描述

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

​​Output Specification:

For each test case, print the total time on a single line.

Sample Input 1:

6 110 1 10

Sample Output 1:

2

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossible

二、解题思路

个人认为这道题还是比较难的，倒不是具体的代码实现难，而是有点难想。给出两个数，及其中一个数的进制，求另外一个数的进制。我们可以把已知进制的数先转换成十进制，进制转换的功能用函数LL change(string str, LL radix)实现。随后查找另一个数的进制。事实上，这是一个考察二分查找的题。下界是很好确定的，我们知道，二进制中的数字不可能有超过1的数，八进制的数字不可能有超过7的数，这样我们就可以确定所求进制的下界。这个功能用函数minRadix(string str)来实现。至于上界，显然，要比下界大，但是一定不会大于另一个数的十进制。上下界确定之后，可以用二分法确定最终的radix，若查找失败，输出“Impossible”。

三、AC代码

#include<iostream> #include<cstdio> #include<string> #include<algorithm> using namespace std; typedef long long LL; LL change(string str, LL radix) { LL tmp, sze = str.size(); LL ans = 0; for(LL i=0; i<sze; i++) { if(str[i]>='a' && str[i] <= 'z') tmp = str[i] - 'a' + 10; else tmp = str[i] - '0'; ans = ans*radix + tmp; } if(ans < 0) return -1; return ans; } int minRadix(string str) { int ans=1, tmp, sze = str.size(); for(int i=0; i<sze; i++) { if(str[i]>='a' && str[i] <= 'z') tmp = str[i] - 'a' + 10; else tmp = str[i] - '0'; if(tmp >= ans) ans = tmp + 1; } return ans; } int main() { string str[2]; int tag; LL radix; LL deci; cin >> str[0] >> str[1] >> tag >> radix; deci = change(str[tag-1], radix); int mk = tag == 1 ? 1 : 0; LL low = minRadix(str[mk]), high = max(deci, low), mid = (high+low)/2, tmp = change(str[mk], mid); while(high >= low) { if(tmp < 0 || tmp > deci) { high = mid - 1; mid = (high+low)/2; } else if(tmp < deci) { low = mid + 1; mid = (high+low)/2; } else break; tmp = change(str[mk], mid); } if(high < low) printf("Impossible"); else printf("%lld", mid); return 0; }