解法参考:https://blog.csdn.net/qq_37613112/article/details/91387345
题目描述
Sample Input
6 110 1 10
Sample Output
2
思路
WA着WA睡着了的一题- -太坎坷了
令已知进制的数为base,所求数为trans。先用radix算出base对应的值num1,再找出答案,这个答案使得未知进制的数对应的值num2==num1
注意点:
-
不用考虑 0 的情况,因为题目里写了输入是4个Positive Integer
-
算值时可能是大数,需要使用long long。别忘了把计算过程中所有涉及到的数的类型都设成long long
-
答案的上下界:
下界应该是所有digit中的最大字符+1
上界应该是num1+1。如果比这个数还大的话,当未知进制的数的位数>=2时,num2必定会大于num1 -
需要使用二分法,因为暴力尝试时用例7会超时
AC代码
#include <iostream>
#include <string>
using namespace std;
/*
* 字符转数值
*/
long long str2int(char c){
if(c>='0'&&c<='9'){
return (long long)(c-'0');
}
return (long long)(c-'a'+10);
}
int main(){
int tag;
long long radix;
string N1,N2;
cin>>N1>>N2>>tag>>radix;
string base = tag==1?N1:N2; //进制已知的数
string trans = tag==1?N2:N1; //进制未知的数
long long num1=0; //进制已知的数对应的值
long long num2 = 0; //进制未知的数对应的值
int len1 = base.size();
int len2 = trans.size();
//num1由数转化为数值
long long rr = 1;
for(int i = len1-1;i>=0;--i){
num1 += str2int(base[i])*rr;
rr *= radix;
}
//确定所求答案的上下界
long long end = num1+1;
long long start = str2int(trans[0]);
for(int i = 0;i<len2;++i){
if(str2int(trans[i])>start)
start = str2int(trans[i]);
}
start += 1;
//二分法找到答案
while(start<=end){
long long redis = (start+end)/2;
rr = 1;
num2 = 0;
for(int j = len2-1;j>=0;--j){
num2 += str2int(trans[j])*rr;
rr *= redis;
}
if(num2<0 || num1<num2){//当前的进制数太大,num2溢出变为负
end = redis-1;
}else if(num1>num2){
start = redis+1;
}else{
cout<<redis;
return 0;
}
}
cout<<"Impossible";
return 0;
}