pat 甲级 1010 Radix (25 point(s))

1010 Radix (25 point(s))

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:

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossible

题意:输入给出两个整数n1,n2,和两个数tag,radix(进制)，如果tag==1，说明radix是n1的进制数，否则则是n2的进制数，如样例 n1=6,n2=110,tag=1,radix=10;

说明radix是n1的进制数，即n1是10进制数，题目要求得是n2是什么进制数才能使得n1==n2,如果n2是2进制数，二进制的110转换成10进制数为6，即满足n1==n2,输出该进制数，即为2；

注意：不能用暴力枚举，即每种进制都试过一次和已知数比看看等不等，这个不行的，因为测试的进制数最大能到INT_MAX去，所以要用二分法减少运算；

思路：先写一个把已知的某进制数转换成10进制数，统一进制好比较，然后用二分查找找该数在该进制的情况下和已知数相等，其实就是判断某个值是否存在且和查找值相等（二分寻找的模板三）

代码：

#include<iostream>
#include<cctype> 
#include<cmath>
#include<algorithm>
using namespace std;
long long convert(string s,long long radix){//把进制为radix的数s转换成10进制数sum,return出来; long long sum=0;int indix=0;for(auto it=s.rbegin();it!=s.rend();it++){//从个位数往前遍历,rebegin指向s的最后一个元素，rend指向s的第一个元素的后一个元素; long long temp=isdigit(*it)?*it-'0':*it-'a'+10;//*it-'a'，算出字母到a之间的距离，然后再加上a（十进制数是10），相当于加回来，就得到该数的十进制数; sum+=temp*pow(radix,indix++);//把每一位都分离出来，乘以其进制的index次方，如二进制数110，分离出来就是0，1，1，按程序运行就是sum=0*2^0+1*2^1+1*2^2=0+2+4=6,为110的10进制数 ;}return sum;
} 
long long find_radix(string n,long long x){char it=*max_element(n.begin(),n.end());//*max_element在algotithm的函数，找区间最大值; long long left=(isdigit(it)?it-'0':it-'a'+10)+1;//找出最大值后算出其十进制数，比方说十进制数123，其最大值为3，3的十进制数就是3，就该数就不可能是3进制，所以下界起码是3+1==4进制，从4开始遍历； long long right=max(left,x);//上界到已知数num就好了;while(left<=right){//因为是要求该数存在并相等，所以最后一次right==left即mid=x存在的情况要遍历出来，return出这个mid,所以是right>=left; long long mid=left+(right-left)/2;//优化一下，目的是防止right+left的时候溢出，写mid=(left+rigtht)/2也可以; if(convert(n,mid)>x||convert(n,mid)<0){//mid进制的情况下，转换成10进制后跟x比较，看看等不等，等就输出mid，mid就是满足条件的最小进制数,计算机组成，正数溢出为负数，此处是考虑了转换成十进制数溢出的情况; right=mid-1;}else if(convert(n,mid)<x){left=mid+1;}else {return mid;}}return -1;
}
int main(){string n1,n2;long long radix,tag; cin>>n1>>n2>>tag>>radix;long long result=(tag==1)?find_radix(n2,convert(n1,radix)):find_radix(n1,convert(n2,radix));if(result==-1){cout<<"Impossible";}else {printf("%lld",result);}return 0;
}

纯净版（可以对照着看）：

代码：

#include<iostream>
#include<cctype> 
#include<cmath>
#include<algorithm>
using namespace std;
long long convert(string s,long long radix){long long sum=0;int indix=0;for(auto it=s.rbegin();it!=s.rend();it++){ long long temp=isdigit(*it)?*it-'0':*it-'a'+10;sum+=temp*pow(radix,indix++);}return sum;
} 
long long find_radix(string n,long long x){char it=*max_element(n.begin(),n.end());long long left=(isdigit(it)?it-'0':it-'a'+10)+1;long long right=max(left,x);while(left<=right){/long long mid=left+(right-left)/2;if(convert(n,mid)>x||convert(n,mid)<0){right=mid-1;}else if(convert(n,mid)<x){left=mid+1;}else {return mid;}}return -1;
}
int main(){string n1,n2;long long radix,tag; cin>>n1>>n2>>tag>>radix;long long result=(tag==1)?find_radix(n2,convert(n1,radix)):find_radix(n1,convert(n2,radix));if(result==-1){cout<<"Impossible";}else {printf("%lld",result);}return 0;
}