PAT甲级真题1010 进制
链接：PAT甲级真题1010 进制
给定一对正整数，例如 6 和 110，此等式 6=110 是否成立？
答案是可以成立，当 6 是十进制数字，110 是二进制数字时等式得到满足。
现在，给定一个正整数数对 N1,N2，并给出其中一个数字的进制，请你求出另一个数字在什么进制下，两数相等成立。
输入格式
输入共一行，包含四个正整数，格式如下：
N1 N2 tag radix
N1 和 N2 是两个不超过 10 位的数字，radix 是其中一个数字的进制，如果 tag 为 1，则 radix 是 N1 的进制，如果 tag 为 2，则 radix 是 N2 的进制。
注意，一个数字的各个位上的数都不会超过它的进制，我们用 0∼9 表示数字 0∼9，用 a∼z 表示 10∼35。
输出格式
输出使得 N1=N2 成立的另一个数字的进制数。
如果等式不可能成立，则输出 Impossible。
如果答案不唯一，则输出更小的进制数。
数据范围
2≤radix≤36
输入样例1：
6 110 1 10
输出样例1：
2
输入样例2：
1 ab 1 2
输出样例2：
Impossible
解题思路
枚举区间很大时，我们会想可不可以用二分求？
当进制变大时数值也一定是变大的，所以这是个单调的过程可以用二分
- 二分的分析：
- 二分的区间
- 左端点：N2数字里最大的那位加1
- 右端点：target + 1
- 使用哪个模板？
知识点：秦九韶算法
LL cal(string str, LL r) { LL res = 0; for (auto c : str) { if ((double)res * r + get(c) > 1e16) return 1e18; res = res * r + get(c); } return res; }
注意判断一下，如果在算最高位时直接大于3610(3∗1015)也就是最大进制，那准定是无解的，直接返回一个更大的比如1e18作为右边界就行。
易错点
- 进制位r也的是long long 类型的
- 二分条件想错了：应该是找大于等于target的最小进制数 if(cal(s2, r)) >= target
- 关于二分的左右边界，还是得正常去找。左边界就是每位数中最大的数加一，右边界就是3610,(3∗1015)，如果在算最高位时直接大于36^10也就是最大进制，那准定是无解的，直接返回一个更大的比如1e18作为右边界就行。
AC代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; LL getn(char i){ if(i<='9')return i - '0'; else return 10 + (i - 'a'); } //转换为10进制 LL cal_10(string n,LL r){ LL res=0; for(auto e : n){ if((double)res*r+getn(e)>1e16) return 1e18; res = res*r + getn(e); } return res; } int main() { string N1 ,N2; LL radix,tag; cin >> N1 >> N2 >> tag >> radix; if(tag==2)swap(N1,N2); LL target = cal_10(N1,radix);//把N1转换为10进制 LL l = 0,r = target+1; for(auto i : N2)l=max(l,(LL)getn(i)+1); //二分判断 while(l<r){ LL mid = l+r>>1; if(cal_10(N2,mid)>=target)r=mid; else l=mid+1; } if(cal_10(N2,r)!=target)cout<<"Impossible"<<endl; else cout << r <<endl; return 0; }
