[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

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议