PAT甲级1010Radix25分/二分法猜进制转换/详细解读精准求出上限下限

爱被打了一巴掌 2024-04-19 09:42 1阅读 0赞

题目来源：[https://pintia.cn/problem-sets/994805342720868352/problems/994805507225665536][https_pintia.cn_problem-sets_994805342720868352_problems_994805507225665536]

代码参考：[https://www.liuchuo.net/archives/2458][https_www.liuchuo.net_archives_2458]

题目大意翻译：已知r进制的数n1,求n2在什么进制能等于n1

解法分析：

假如已经能想到先将n1换成十进制数，然后就该测试n2的进制了  
难点：  
1.目标进制的下限是n2的最大位数的十进制数+1。如果没有+1，那最大位数会进位。

2.目标进制的上限是n1的十进制和下限中较大那个。不要因为题目说两个数字用的数最大是z就以为进制最大是36。

*  在n1的十进制大于下限的时候，n2为个位数的时候还是表示本身，但是一旦是两位数，就肯定超过n1的十进制数了（至少是n1加1）。
 *  在n1的十进制小于等于下限的时候，n1和n2肯定都是个位数，这个情况也不用继续求了。所求的可能的最小进制就是下限。

3.考虑进制转换后溢出成为负数。

//AC代码如下：
    #include<iostream>
    #include<algorithm>
    using namespace std;
    long long  Convert(string n1,long long radix){
        int l1 = (int)n1.length();
        long long in1=0,j=1;
        for(int i=l1-1;i>=0;i--){
            if(isdigit(n1[i]))in1+=(long long)(n1[i]-'0')*j;
            else in1+=(long long)(n1[i]-'a'+10)*j;
            j*=radix;
        }
        return in1;
    }
    long long FindRadix(long long n1,string n2){
        long long res = -1;
        char it=*max_element(n2.begin(), n2.end());
        long long low=(isdigit(it)?it-'0':it-'a'+10)+1;//进制下限
        long long high=max(n1,low);//进制上限
        while(low<=high){
            long long mid=(low+high)/2;
            res = Convert(n2, mid);
            if(res==n1)return mid;
            else if(res<0 || res>n1)high=mid-1;//res<0 表示转换后溢出
            else low=mid+1;
        }
        return -1;
    }
    int main(){
        string n1,n2,n3;
        long long tag,radix,in1;
        cin>>n1>>n2>>tag>>radix;
        if(tag==2)swap(n1, n2);
        in1=Convert(n1,radix);
        long long guess=FindRadix(in1,n2);
        if(guess==-1)cout<<"Impossible";
        else cout<<guess;
        return 0;
    }

[https_pintia.cn_problem-sets_994805342720868352_problems_994805507225665536]: https://pintia.cn/problem-sets/994805342720868352/problems/994805507225665536
[https_www.liuchuo.net_archives_2458]: https://www.liuchuo.net/archives/2458

发表评论取消回复

表情：

评论列表（有 0 条评论，1人围观）

还没有评论，来说两句吧...

相关阅读

相关 PAT甲级1010Radix25分/二分法猜进制转换/详细解读精准求出上限下限

目来源：[https://pintia.cn/problem-sets/994805342720868352/problems/994805507225665536][h...

爱被打了一巴掌/ 2024年04月19日 09:42/ 0 赞/ 2 阅读

相关 PAT 甲级 1075 PAT Judge (25 分) 铭记

1075 PAT Judge (25 分) The ranklist of PAT is generated from the status list, which sh

本是古典何须时尚/ 2024年02月19日 21:33/ 0 赞/ 6 阅读

相关 PAT 甲级 1003 Emergency (25 分)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

红太狼/ 2023年08月17日 16:03/ 0 赞/ 61 阅读

相关 PAT乙级：1010 一元多项式求导 (25 分)

PAT乙级：1010 一元多项式求导 (25 分)（Java）微信公众号请搜索：【Codeplus】 > 作者 DS课程组 > 单位浙江大学 > 代码长

我不是女神ヾ/ 2022年10月15日 10:56/ 0 赞/ 141 阅读

相关 PAT甲级-1010. Radix (25)进制

1010. Radix (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standa

柔光的暖阳◎/ 2022年05月31日 09:52/ 0 赞/ 112 阅读

相关 1010. Radix (25)

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be

「爱情、让人受尽委屈。」/ 2022年05月31日 07:28/ 0 赞/ 91 阅读

相关 PAT甲级 - 1003 Emergency （25 分）

题目链接：[（PAT甲级）1003 Emergency （25 分）][PAT_1003 Emergency _25] As an emergency rescue team

太过爱你忘了你带给我的痛/ 2022年03月19日 16:26/ 0 赞/ 148 阅读

相关 PAT甲级 - 1010 Radix （25 分）

题目链接：[PAT甲级 - 1010 Radix （25 分）][PAT_ - 1010 Radix _25] Given a pair of positive intege

╰半橙微兮°/ 2022年03月18日 04:48/ 0 赞/ 167 阅读

相关 PAT甲级 - 1021 Deepest Root （25 分）

题目链接：[PAT甲级 - 1021 Deepest Root （25 分）][PAT_ - 1021 Deepest Root _25] A graph which is

左手的ㄟ右手/ 2022年03月17日 01:16/ 0 赞/ 131 阅读

相关 PAT 1010 一元多项式求导 (25分)（Java）

题目描述 ![设计函数求一元多项式的导数。（注：xn （n为整数）的一阶导数为nxn−1 。）][x_n_ _n_nx_n_1_] 输入格式: 以

刺骨的言语ヽ痛彻心扉/ 2021年09月24日 01:58/ 0 赞/ 264 阅读