【题意】

读入俩数n1和n2，以及1或2的tag标签，还有一个进制数radix（2到36的整数）；若tag为1，那么表示n1为radix进制的数，求n2为何进制时，与n1等值；注意n1、n2数位上的数可以为小写英文字母（a∼z 表示 10∼35）。

【原题链接】

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

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数字混字母，肯定得用string等字符容器来存，并且在计算过程中字母需要统一转为数字；对于给出明确数字与进制的那一个，可以转为十进制，然后用二分法为另一位数匹配其进制数；

需要注意另一个数的进制，最大可能为已知数的十进制值+1，另外使用的数据类型，也要根据最大的数值可能范围选择，可以说坑点多多了。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
long long get(char a){
//字符转数字处理
if(a<='9') return a-'0';
else return a-'a'+10;
}
long long cal(string a,long long r){
//任何进制数，转十进制数处理
long long res=0;
for(auto c:a){
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);
long long target=cal(n1,radix);
long long l=0,r=max(target+1,36ll);
//int型末加ll，转为long long同型比较
for(auto c:n2) l=max(l,get(c)+1);
//+1是进值要比n2的每一位都大
while(l<r){
//二分遍历匹配进制
long long mid=l+r>>1;
if(cal(n2,mid)>=target) r=mid;
//若进制取大了，会缩小范围的，以保证多解下取最小的进制
else l=mid+1;
}
if(cal(n2,r)!=target) cout<<"Impossible";
else cout<<r;
return 0;
}

最后

以上就是苹果裙子为你收集整理的【PAT甲级】1010 Radix 进制匹配【题意】【原题链接】【题解】 的全部内容，希望文章能够帮你解决【PAT甲级】1010 Radix 进制匹配【题意】【原题链接】【题解】 所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。