题目
题目链接
N1 N2 tag radix
tag为0，radix表示N1的进制。tag为1，radix表示N2的进制
已知一个确定进制的数字，求另一个数字的进制，使两个数字转换为十进制后相等
题目分析
已知两个数（最多有10位），其中一个数的基数，求使两个数相等的另一个数的基数，
解题思路
1 二分查找，寻找另一个数的基数，使得两个数字十进制相等
易错点
1 已知数字最多有10位，如果基数大于10，可能会超过int范围，需要使用long long
2 未确定进制的数字，转换为10进制可能long long 溢出（为负值），表示基数太大要right=mid-1（若没有该判断，测试点：10 12 13 15 16 6 8会错误）
3 每位用0-9，a-z表示，但是进制最大并不是36，而是可以很大，最大为INT_MAX。所以必须使用二分查找。暴力枚举会超时，需要使用二分查找
4 未知基数数字的进制，下界为所有数位中最大数+1，上界为max{基准数十进制，下界}（如：100000 10第一个数字基数为10，第二个数字基数为1000000也能使两个数相等）
知识点
1 二分查找非递归写法
2 任意进制转换为十进制
long long conver_radix(long long radix,string vs) {
long long ans = 0,index=0;
for(int i=vs.length()-1; i>=0; i--) {
int temp=isdigit(vs[i])?vs[i]-'0':vs[i]-'a'+10;
ans += temp*pow(radix,index++);
}
return ans;
}
Code
Code 01
#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
/*
错误1：已知进制的数字转换为十进制 可能溢出int范围
错误2：每位用0-9，a-z表示，但是进制最大并不是36，而是可以很大，最大为INT_MAX。所以必须使用二分查找
错误3：进制边界不是2~INT_MAX，下界取最大数字+1，上界取 max{下界,该数十进制}+1
错误4：未确定进制的数字，转换为10进制可能long long 溢出
*/
// 进制转换----从其他进制转换为十进制
LL convert(string s,LL r) {
LL sum=0,index=0;
for(int i=s.length()-1; i>=0; i--) {
LL temp = isdigit(s[i])?s[i]-'0':s[i]-'a'+10;
sum+=temp*pow(r,index++);
}
return sum;
}
// 二分查找---查找合适进制
int find_radix(string x, LL v,LL left,LL right) {
while(left<=right) {
LL mid=left+((right-left)>>1);
LL temp = convert(x,mid);
if(temp==v) {
return mid;
} else if(temp>v||temp<0) {
right=mid-1;
} else {
left=mid+1;
}
}
return -1;
}
// 未确定进制的数字出现最大的字符表示的数字
int find_max_digit(string m){
int ans=-1;
for(int i=0;i<m.length();i++){
int temp = isdigit(m[i])?m[i]-'0':m[i]-'a';
if(temp>ans)ans=temp;
}
return ans;
}
int main(int argc, char * argv[]) {
int f,r;
string n1,n2;
cin>>n1>>n2>>f>>r;
LL n;string m;
if(f==1){
n=convert(n1,r);
m=n2;
}else{
n=convert(n2,r);
m=n1;
}
LL left = find_max_digit(m)+1; //未确定进制的数字出现最大的字符表示的数字+1
LL right = n+1; //已确定进制的数字的十进制数值+1
LL radix = find_radix(m,n,left,right); // 二分查找进制
if(radix==-1)printf("Impossible
");
else printf("%d
",radix);
return 0;
}
Code 02
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <climits>
using namespace std;
long long conver_radix(long long radix,string vs) {
long long ans = 0,index=0;
for(int i=vs.length()-1; i>=0; i--) {
int temp=isdigit(vs[i])?vs[i]-'0':vs[i]-'a'+10;
ans += temp*pow(radix,index++);
}
return ans;
}
int main(int argc,char * argv[]) {
string N1,N2,w,y;
long long tag,radix;
cin>>N1>>N2>>tag>>radix;
if(tag==1) w=N2,y=N1;
else w=N1,y=N2;
long long ys=conver_radix(radix,y); //已知进制数的十进制
char it = *max_element(w.begin(),w.end());
long long low=(isdigit(it)?it-'0':it-'a'+10)+1; //进制下界：找到最大数字+1, 若最大数字为9，那么最小进制应该为10
long long high=max(low,ys); //进制上界：基准十进制数与下界取较大，INT_MAX不对，第一个测试点错误
long long m = low+((high-low)>>1);
while(low<=high) {// 二分查找
m = low+((high-low)>>1);
// m作为基数，转换数字到十进制，与另外一个数字十进制比较
long long ws = conver_radix(m,w);
if(ws==ys) {
break;
} else if(ws<0||ws>ys) {
high=m-1;
} else {
low=m+1;
}
}
if(low>high)printf("Impossible");
else printf("%d",m);
return 0;
}