[PAT解题报告] Radix
题目给定两个“数”，已知其中一个数是w进制的，问另外一个数是几进制才能使得这两个数相等。所有数长度不超过10，每一位只有0-9还有a-z。首先题目没给数据范围，我们先把第一个w进制的数化成10进制的整数，注意用long
long——好在范围够用。下面考虑另外一个数的进制，关键问题在进制可以很大，比如11这个数，在3610进制中会达到(3610+1)那么大，所以我们还是要慎重考虑进制。好在进制可以二分，我们二分一个进制b,然后把第一个数x化成b进制数存到数组里，和第二个数比一下看看是不是一样，因为我们选择的b越大，x转换过来的数“形式”上越小,所以这个是有单调性的。我们总可以找到最小的b，让x转换过来等于我们想要的数。
注意点： 要使用long long， 因为b是long long的，所以每一位也能到(b -
1)那么大，因此数组也要用long
long类型。另外就是二分的左端点的选择不一定是1，例如第二个数包含数字“5”，那么至少b要选择6进制……所以左边界应该是不知道进制的那个数每一位数字最大的加1。
代码有点长：
#include <cstdio>
#include <cstring>
#include <string>
#include <cctype>
#include <vector>
using namespace std;
char s[2][12];
long long change(const char *s,int b) {
long long x = 0;
for (; *s; ++s) {
x *= b;
x += isdigit(*s)?(*s - '0'):(*s - 'a' + 10);
}
return x;
}
vector<long long> make(long long x, long long b) {
vector<long long> c;
do {
c.push_back(x % b);
x /= b;
} while (x);
return c;
}
int cmp(const vector<long long> &a,const vector<long long> &b) {
if (a.size() > b.size()) {
return 1;
}
if (a.size() < b.size()) {
return -1;
}
for (int i = a.size() - 1; i >= 0; --i) {
if (a[i] > b[i]) {
return 1;
}
if (a[i] < b[i]) {
return -1;
}
}
return 0;
}
int main() {
int ind,b;
scanf("%s%s%d%d",s[0],s[1],&ind,&b);
long long x = change(s[--ind], b);
ind ^= 1;
b = 1;
int len = strlen(s[ind]);
vector<long long> a(len);
for (int i = 0; i < len; ++i) {
b = max(b, (int) (a[len - 1 - i] = isdigit(s[ind][i])?(s[ind][i] - '0'):(s[ind][i] - 'a' + 10)));
}
long long answer = -1,left = b + 1, right = (left > x)?left:x;
while (left <= right) {
long long mid = ((right - left) >> 1) + left;
vector<long long> c = make(x, mid);
int result = cmp(a, c);
if (result == 0) {
answer = mid;
}
if (result >= 0) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
if (answer < 0) {
puts("Impossible");
}
else {
printf("%lld\n",answer);
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1010
上海黑芝麻智能二面2人在聊
查看13道真题和解析
