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: 2 Sample Input 2: 1 ab 1 2 Sample Output 2: Impossible分析： 题目就是让n1或者n2其中一个为给定的radix进制数，找出另一个数的进制，让他们两相等。思路就是先让n[tag]转为radix进制，然后使用二分遍历找到目标radix，过程中主要注意以下几点。
long long 型而不是int型。输入的数字有10位，所以用int可能会溢出，在本题中尽量用longlong。遍历基数的上下限。下限应该是n[3-tag]（因为要不就n1,要不就n2）中最小的一位+1，如果等于基数就要进位,可以用max_element()。上限应该是n[tag]和 下限的最大值（比如 9 9 1 10）下限为10，而n[tag]为9。；求出的基数使他们相等就是最小的基数，二进制正数溢出会变成负数。 //下限 char it = *max_element(n[3-tag].begin(),n[3-tag].end()); ll left = isdigit(it)? it - '0' +1: it-'a'+10+1; //上限AC代码：
#include<iostream> #include<vector> #include<cstring> #include<algorithm> #include<cctype> #include<cmath> using namespace std; typedef long long ll; string n[3]; ll tag,radix; ll decimal(string s,ll r){ ll temp = 0; for (int i = 0; i < s.size(); ++i) { temp *= r; if(s[i] >= 'a'&&s[i] <='z'){ temp += (s[i] - 'a')+10; }else if(isdigit(s[i])){ temp += s[i] - '0'; } } return temp; } int main(int argc, char const *argv[]) { cin>>n[1]>>n[2]>>tag>>radix; ll n1 = decimal(n[tag],radix); //cout<<n1<<endl; char it = *max_element(n[3-tag].begin(), n[3-tag].end()); ll low = (isdigit(it) ? it - '0': it - 'a' + 10) + 1; ll right = max(n1, low); ll re = -1; while(low <= right){ ll mid = (low + right)/2; ll n2 = decimal(n[3-tag],mid); if(n2 > n1||n2<0){ //n2<0代表基数太大了 right = mid-1; }else if(n1 == n2){ re = mid; break; }else { low = mid+1; } //cout<<mid<<' '<<n1<<' '<<n2<<endl; } if(re < 0) cout<<"Impossible"<<endl; else cout<<re<<endl; return 0;感动天，感动滴，终于被我调出来了，害太难了QTQ
这里补充一下二分查找：
function binarry(int left, int right, int[] array){ while(left <= right){ int mid = (left + right)/2; if(key == array[mid]) return mid; else if(key > array[mid]) left = mid + 1; else right = mid - 1; } return -1; }```