[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