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

思路

核心：进制的转换，将数转换为10进制然后进行比较即可，需要注意转换会出现溢出的情况

直接循环查找会出现timeout情况，使用二分查找，需要注意begin的取值，数字中最大的字符的数值+1

，max_element(begin,end)：返回迭代器，该迭代器指向范围[begin,end)中的最大元素

Code（参考柳婼）

#include <iostream> #include <algorithm> #include <math.h> using namespace std; long long convert(string n, long long radix){ // radix进制的数转换为10进制数 long long res = 0; int i = 0; int index = 0; for (i=n.size()-1; i>=0; i--){ int temp = isdigit(n[i])? n[i]-'0':n[i]-'a'+10; res += temp * pow(radix,index++); } return res; } long long find_radix(string n, long long sum){ char max_char = *max_element(n.begin(),n.end()); // 返回迭代器，* 取值 long long begin = (isdigit(max_char)?max_char-'0':max_char-'a'+10)+1; // 注意要加1，最小的进制肯定比他自身的字符要大 long long last = max(sum,begin); // for (long long i = begin; i<last; i++){ // // cout << "转化后的数字为：" << convert(n,i) << "进制数为："<< i <<endl; // if (convert(n,i) == sum) // return i; // if (convert(n,i)<0) // 溢出 // break; // } while (begin<=last){ long long mid = (begin+last)/2; long long temp = convert(n,mid); if (temp <0 || temp >sum) last = mid-1; else if (temp == sum) return mid; else begin = mid+1; } return -1; } int main(){ string n1,n2; long long tag,radix; cin >> n1 >> n2>>tag>>radix; long long flag = tag==1?find_radix(n2, convert(n1,radix)):find_radix(n1, convert(n2,radix)); if (flag != -1) cout << flag; else cout << "Impossible"; return 0; }