PAT甲级 - 1010 Radix(思维+二分)

Link

题意：大概意思就是，tag==1，则N1为radix进制的数；tag==2，则N2为radix进制的数。试问另一个数为多少进制的数才能使得N1==N2，无解输出"Impossible"。

思路：基本思路很简单，直接枚举另外一个数的进制即可，期间在进行进制的转换时需要注意许多细节。但如果直接枚举的话将有个测试点(1分)无法通过，不难看出其实进制的取值我们就可以通过二分来查询，其二分的下限即是另一个数的最大位数值maxx+1，上限即位radix进制数的十进制数值+1。（如果误将Impossible输出成impossible则只有18分┭┮﹏┭┮）。

AC代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f3f;
const int N = 1e5+10;

string a, b;
int x, y, tag, radix, maxx, ans=inf;
map<int, char> mp;

int get_int(char x){
    if(isdigit(x)) return x-'0';
    return x-'a'+10;
}

int to_int(string s, int k){
    int res = 0;
    res = get_int(s[0]);
    for(int i = 1; i < s.size(); i ++){
        res *= k;
        res += get_int(s[i]);
    }
    return res;
}

bool check(int k){
    int res = get_int(b[0]);
    for(int i = 1; i < b.size(); i ++){
        res *= k;
        res += get_int(b[i]);
        if(res<0||res>x) return 1;
    }

    if(res==x){
        ans = min(ans, k);
        return 1;
    }
    if(res<0||res>x) return 1;
    else return 0;
}

signed main()
{
    cin >> a >> b >> tag >> radix;
    if(tag==2) swap(a, b);
    x = to_int(a, radix);
    for(int i = 0; i < b.size(); i ++) maxx = max(maxx, get_int(b[i]));
    int l = maxx+1, r = x+1;
    while(l<=r){
        int mid = (l+r)>>1;
        if(check(mid)) r = mid-1;
        else l = mid+1;
    }
    if(ans==inf) cout << "Impossible" << endl;
    else cout << ans << endl;

    return 0;
}