1010 Radix

--write by zhuwx 2019-08-07 09:12:25 +0800 CST

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

转自:https://blog.csdn.net/CV_Jason/article/details/80993283

题目的大意是,给你两个数,N1和N2,给定其中一个数的基数,然后求另一个数的基数,使得两个数相等。
  其实这个题是有点扯淡的,一开始一直有几个测试点通不过,后来提交了无数次,也没有全部通过,查了一堆资料,发现这道题很多信息没有交代清楚,通过测试得到一些隐藏条件和结论,感觉好坑,把做题过程总结一下吧:
  首先要注意,N1和N2最长为十位,取值从’0-9’和’a-z’选,表示十进制的0~35数,但是基数不受此限制,我最开始以为基数也是0-35选数,那么也就是说2-36进制,这么小的范围进行遍历即可,但实际上,题目中并没有说明基数的取值范围,理论上是2到无穷大都可以。那么就产生两个问题:

上溢,十位的数据,如果选用基数较大的话,即便是用64位的long long也会产生上溢(Overflow),那么怎么处理溢出呢?
基数的上限,我们总不可能从2开始遍历,一个一个的尝试,如果能给出一个范围的话,还可以采用二分法缩小查找时间(不然肯定会超时的)

  基于以上考虑,我们在运算中可以全程使用string,而不是long long作为运算的类型,来解决溢出的问题。但是从N进制到十进制,再到string的转化,未免太麻烦了。经过大量提交,至少有一个结论是——题目中给出测试点的已知基数,是不会溢出的。那么另一个未知数据则会产生溢出,尤其是在查找基数的过程中。那么如何表示这个病态数?有一个小技巧,整型有符号数上溢之后会有一个循环现象,比如说:int a = pow(2,31); 刚好比int所能存储的最大正值2^31 - 1 = 2147483647 大1,显示的结果刚好是int所能存储的最小负值-2^31 = -2147483648 ,也就是说,给出的已知数据是不会溢出的,那么只要是取值为负的,全部是上溢,基数取得过大了。
  对于基数范围,首先,可以可以遍历位置数的每一位,得到单个位的最大数,不管是几进制,基数肯定比这个最大值大,这是基数的取值下限。然后,对于已知数,基数肯定不可能大于已知数,这是基数的取值上限。但,显然上限有点高,遍历的话会超时,所以采用二分法。
  结合以上两点分析,参考了网上许多大神的代码,终于是通过了,只能说这道题看似简单,但是想拿全部 25分,有难度。
  最后,对系统类库的正确使用,也能大大提高编程效率。

#include<iostream>
#include<cctype>
#include<algorithm>
#include<cmath>

using namespace std;
// Enter a string and convert to a number
long long str2num(string str,int radix){
long long sum = 0;
int index = 0;
int per_digit = 0;
for(auto t = str.rbegin();t!=str.rend();t++){
per_digit = isdigit(*t)? *t - '0':*t - 'a' + 10;
sum+=per_digit*pow(radix,index++);
}
return sum;
}
// Enter the known and unknown numbers to find the result radix
long long find_radix(string str,long long num){
//cout<<"str = "<<str<<endl;
long long result_radix = -1;
char it = *max_element(str.begin(),str.end());
long long low = (isdigit(it)?it - '0':it - 'a' + 10) + 1;
//cout<<"low = "<<low<<endl;
long long high = max(low,num);
while(low<=high){
long long mid = (low+high)/2;
long long temp = str2num(str,mid);
/*
cout<<"mid = "<<mid<<endl;
cout<<"temp = "<<temp<<endl;
cout<<"low = " <<low<<endl;
cout<<"high = "<<high<<endl;
*/
if(temp<0||temp>num){
high = mid - 1;
}else if(temp<num){
low = mid + 1;
}else{
result_radix = mid;
break;
}
}
return result_radix;

}

int main(){
string N1;
string N2;
int tag;
long long radix;
while(cin>>N1>>N2>>tag>>radix){
long long known_num = (tag==1?str2num(N1,radix):str2num(N2,radix));
long long result = find_radix((tag==1?N2:N1),known_num);
if(result!=-1){
cout<<result<<endl;
}else{
cout<<"Impossible"<<endl;
}
}
return 0;
}