题意
给出两个数和其中一个数的进制，若另一个数存在一个进制使得其根据进制转换之后等于第一个数，则输出进制，否则输出Impossible
初始思路
进制从2~36遍历，到转换后的数已经大于了第一个数之后还找不到相等情况则Impossible
第一次提交
#include
#include
using namespace std;
long long trans(string s,int radix){
long long ans=0;
int len = s.length();
for(int i=len-1;i>=0;i--){
int tmp;
if(s[i]>='0'&&s[i]<='9')
tmp = s[i]-'0';
else
tmp = s[i]-'a'+10;
if(tmp>=radix) return -1;
ans+=tmp*pow(radix,len-i-1);
}
return ans;
}
int main(){
string n,m;
int tag,r;
long long model;
cin>>n>>m;
scanf("%d %d",&tag,&r);
if(tag==2)
swap(n,m);
model = trans(n,r);
int i;
for(i=2;i<=36;i++){
long long tmp = trans(m,i);
if(tmp==model){
printf("%d",i);
return 0;
}
if(tmp>model){
printf("Impossible");
return 0;
}
}
return 0;
}
测试点3 4 5 7 10 11没过 存在的问题
遍历进制的上界我以为是36，其实不是，多大都可以，所以根据每次输入的特性，给一个上界很重要。
然后我就发现，这道题遍历上界可能会很大，所以要采用二分降低时间复杂度
Copy了别人的AC代码
#include
#include
#include
#include
using namespace std;
long long convert(string n, long long radix) {
long long sum = 0;
int index = 0, temp = 0;
for (auto it = n.rbegin(); it != n.rend(); it++) {
temp = isdigit(*it) ? *it - '0' : *it - 'a' + 10;
sum += temp * pow(radix, index++);
}
return sum;
}
long long find_radix(string n, long long num) {
char it = *max_element(n.begin(), n.end());
long long low = (isdigit(it) ? it - '0': it - 'a' + 10) + 1;
long long high = max(num, low);
while (low <= high) {
long long mid = (low + high) / 2;
long long t = convert(n, mid);
if (t < 0 || t > num) high = mid - 1;
else if (t == num) return mid;
else low = mid + 1;
}
return -1;
}
int main() {
string n1, n2;
long long tag = 0, radix = 0, result_radix;
cin >> n1 >> n2 >> tag >> radix;
result_radix = tag == 1 ? find_radix(n2, convert(n1, radix)) : find_radix(n1, convert(n2, radix));
if (result_radix != -1) {
printf("%lld", result_radix);
} else {
printf("Impossible");
}
return 0;
}
学习点：
容器反向迭代器： rbegin：指向容器尾元素 rend：指向首元素前一位置 从后向前迭代isdigit(c) 在cctype头文件中 判断字符型是否是数字max_element()/min_element()
Returns an iterator pointing to the element with the largest value in the range [first,last).
在头文件 #include
学习二分法的上下界确定。对于基数范围，首先，可以可以遍历位置数的每一位，得到单个位的最大数，不管是几进制，基数肯定比这个最大值大，这是基数的取值下限。然后，对于已知数，基数肯定不可能大于已知数，这是基数的取值上限。但，显然上限有点高，遍历的话会超时，所以采用二分法。经过大量提交，至少有一个结论是——题目中给出测试点的已知基数，是不会溢出的。那么另一个未知数据则会产生溢出，尤其是在查找基数的过程中。那么如何表示这个病态数？有一个小技巧，整型有符号数上溢之后会有一个循环现象，比如说：int a = pow(2,31); 刚好比int所能存储的最大正值2^31 - 1 = 2147483647 大1，显示的结果刚好是int所能存储的最小负值-2^31 = -2147483648 ，也就是说，给出的已知数据是不会溢出的，那么只要是取值为负的，全部是上溢，基数取得过大了。