【PAT甲级 - C++题解】1010 Radix

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

Sample Output 1:

2

Sample Input 2:

1 ab 1 2
• 1

Sample Output 2:

Impossible

题意

N1 和 N 2 N2N2 是两个不超过 10 1010 位的数字，radix 是其中一个数字的进制，如果 tag 为 1 11，则 radix 是 N 1 N1N1 的进制，如果 tag 为 2 22，则 radix 是 N 2 N2N2 的进制。

输出使得 N 1 = N 2 N1=N2N1=N2 成立的另一个数字的进制数。

如果等式不可能成立，则输出 Impossible。

如果答案不唯一，则输出更小的进制数。

思路

这道题涉及到了秦九韶算法：

假设给定一个 d 进制 abc ，那么我要转化成十进制的公式为：a∗d2+b∗d1+c ，放到循环中其实就是：

//假设n为字符串
long long res = 0;
for(auto x : n)
  res = res * d + x - '0';

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//将字符转换成数字
int get(char c)
{
    if (c <= '9')  return c - '0';
    return c - 'a' + 10;
}
//获得十进制值
LL calc(string n, LL r)
{
    LL res = 0;
    for (auto c : n)
    {
        //double存的数字比long long更大
        //如果已经大于1e16则一定大于target，直接返回一个超大值即可
        if ((double)res * r + get(c) > 1e16) return 1e18;
        res = res * r + get(c); //秦九韶算法
    }
    return res;
}
int main()
{
    string n1, n2;
    cin >> n1 >> n2;
    int tag, radix;
    cin >> tag >> radix;
    if (tag == 2)  swap(n1, n2);    //统一化处理
    LL target = calc(n1, radix);    //获得n1的十进制
    //获得二分的上边界和下边界
    LL l = 0, r = max(target, 36ll);
    for (auto c : n2)  l = max(l, (LL)get(c) + 1);
    //二分查找
    while (l < r)
    {
        LL mid = l + r >> 1;
        if (calc(n2, mid) >= target) r = mid;
        else    l = mid + 1;
    }
    if (calc(n2, r) == target) cout << r << endl;
    else puts("Impossible");
    return 0;
}