PAT甲级1010题（进制）

进制题

PAT

发布日期: 2021-02-23

文章字数: 198

阅读时长: 1 分

阅读次数:

1.题目介绍

1010

2.考察点，难度

进制题，long long数据类型，进制转换，特判，二分查找，难度难。

3.解题代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;


int get(char c){
    if(c<='9') return c-'0';
    return c-'a'+10;
}

LL calc(string n, LL r){
    LL sum=0;
    for(auto c:n){
        if ((double)sum * r + get(c) > 1e16) return 1e18;
        sum=sum*r+get(c);
    }
    return sum;
}

int main(){
    string n1,n2;
    int tag,radix;
    cin>>n1>>n2>>tag>>radix;
    if(tag==2)  swap(n1,n2);
    LL target=calc(n1,radix);
    LL l=0,r=target+2;
    for(auto s:n2){
        l=max(l,(LL)get(s)+1);
    }
    while(l<r){
        LL mid= l+r>>1;
        if(calc(n2,mid)>=target) r=mid;
        else    l=mid+1;
    }
    if(calc(n2,r)!=target)   puts("Impossible");
    else    cout<<r<<endl;
    return 0;
}