1482. 进制
算法( 枚举 + 二分查找 + 进位制)
由题意可知该题需要通过不断模拟找到n1与n2相等的进制值,但数据范围比较大,一个个模拟可能会超时,则需要通过二分来不断缩小进制范围来得出答案
步骤
- 录入数据,将已经给出进制的数当作n1
- 将(n1)idx转换为(n1)10,由此与36取最大值可确定右边界范围
- 找到左边界,最小进制应该为n1各位数字最大值+1
- 开始二分,不断缩小二分范围,当到边界时,判断当n2为该边界下进制的十进制值时是否与(n1)10相等
- 相等则对应输出,不相等则输出Impossible
疑问
- 为什么进制要用LL存储?
因为题目只给出了N1,N2其中的一个进制,我们并不知道另一个进制的范围,因此第二个进制范围最大值可能为35^10,此时已经超了int的范围,所以需要用long long。 - 为什么在判断溢出条件时需要res需要强转为double
因为double表示的数据范围比long long大得多,可以判断是否溢出
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int get(char c)
{
if (c <= '9') return c - '0';
return c - 'a' + 10;
}
LL calc(string n, LL r)
{
double res = 0;
for (auto c : n)
{
//double可以表示比long long更大的整数范围,因此可先用double强转判断是否溢出
if ((double)res * r + get(c) > 1e16) return 1e18;
res = res * r + get(c);
}
return (LL)res;
}
int main()
{
string n1, n2;
cin >> n1 >> n2;
int tag, radix;
cin >> tag >> radix;
if (tag == 2) swap(n1, n2);
LL target = calc(n1, radix);
//左边界为2(最小进制) 右边界最大为target的值与36ll的最大值
LL l = 2, r = max(target, 36ll);
for (auto c : n2) l = max(l, (LL)get(c) + 1);//获取左边界(最小进制)
while (l < r)
{
LL mid = l + r >> 1;
if (calc(n2, mid) >= target) r = mid;
else l = mid + 1;
}
if (calc(n2, r) != target) puts("Impossible");
else cout << r << endl;
return 0;
}