PAT-A 真题- 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

题目大意：给定四个输入，前两个是数字，第三个是标签，第四个是进制。当标签为1时，进制指的是第1个数字的进制，标签为2时，进制指的是第二个数字的进制。

要求判断能不能将另一个数，转成n进制，与所给的标签对应的数字相等，如果能，输出n，如果不能，输出Impossible。

所给数字最大可能是10位数。

这是一个进制转换类问题，首先要注意的是，数字最大可能是10位数，因此不能用int存储数字，必须使用long long。

另外，对于10进制以上，输入中就会包含a-z，所以读取输入应当使用string或char[]

此外，数字最大可能是10位数，进制也可能会非常大，如果线性判断会导致三个测试点超时，必须使用二分法来判断，判断的思路是，定义一个上界和下界，每次取mid=(上界+下界)/2为进制进行判断。如果转换进制后的数字比要进行判断的数字（标签对应数字）大，则说明进制选取过大，应减小上界，令上界=min-1即可，反之亦然。

初始下界的选取应根据输入数字中最大的数字来判断，比如12358不可能是7进制的，最小也是9进制

初始上界应该比初始下界大，并且小于要进行判断的数字。

代码如下：

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;

int toDig(char c){
  if(c <= '9' && c >= '0')
    return c - '0';
  else return c - 'a' + 10;
}

long long StrToRx(string num, long long radix){
  long long ans = 0;
  for(int i = num.length()-1, p = 0; i >= 0; i--, p++){
    ans += toDig(num[i]) * pow(radix, p);
  }
  return ans;
}

int main(){
  string input[2];
  cin >> input[0] >> input[1];
  int tag;
  long long radix;
  cin >> tag >> radix;
  long long num = StrToRx(input[tag-1], radix);
  string _num = input[tag%2];
  char it = *max_element(_num.begin(), _num.end());
  long long down = (isdigit(it) ? it - '0': it - 'a' + 10) + 1;
  long long up = max(num, down);
  while(down <= up){
    long long mid = (down+up) / 2;
    long long rx = StrToRx(_num, mid);
    if(rx == num){
      cout << mid << endl;
      return 0;
    }else if(rx < 0 || rx > num){
      up = mid - 1;
    }else{
      down = mid + 1;
    }
  }
  cout << "Impossible" << endl;
  return 0;
}