Closer's Space

梦河之上, 一叶扁舟

pat甲级1010


pat的数据范围真的迷....

细节

  • 答案可能大于36, 要注意范围
  • 用二分降低复杂度, 选好边界

c++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull inf = (1ULL << 63);

int toInt(char x){
        return x > '9' ? x - 'a' + 10 : x - '0';
}

ull stringToInt(string s, ull x, ull tmp){
        ull res = 0;
        for(int i = 0; s[i]; ++i){
                int cur = toInt(s[i]);
                //溢出处理
                if(res >= (inf - cur) / x || res > tmp) return inf;
                res = res * x + cur;
        }
        return res;
}

ull cal(string s){
        ull res = 0;
        for(int i = 0; s[i]; ++i)
                res = max(res, (ull)toInt(s[i]));
        return res;
}

int main(){
        //freopen("in.txt", "r", stdin);
        string a, b;
        int tag, radix;
        cin >> a >> b >> tag >> radix;
        if(tag == 1) swap(a, b);
        ull s = stringToInt(b, radix, inf);
        ull l = cal(a), r = s + 2;//左右边界
        while(l < r - 1){
                ull m = (l + r) >> 1;
                ull cur = stringToInt(a, m, s);
                if(cur == s){
                        cout << m << endl;
                        return 0;
                }
                if(cur > s) r = m;
                else l = m;
        }
        cout << "Impossible" << endl;;
        return 0;
}

博文最后更新时间:


评论

  • 暂无评论

发表评论

来访统计

访问量:259

评论总数:0