PAT甲级1010 Radix ：[C++题解]进制位、秦九韶算法、二分（PAT通过率最低的一道题0.11）

文章目录

• • 题目分析
  • 题目链接

题目分析

分析：

本题思路分两步。
第一步：先把给出数值和进制的数，暂定为N1，转换成10进制，即为target。

第二步： 判断一下N2在多少进制下是等于target的。

然后看一下数据范围。

给的进制数最大是36进制，数最多是10位，因此N1最大可能是$36^{10}<1\times 10^{16}$ 会爆int，用long long （范围$9\times 10^{18}$）来存。

第二个数N2的进制数最大是多少呢？ 当N2的位数很少的时候，它的进制数会很大，最大跟N1十进制下的最大值差不多，比如$(10{)}_{radix}=1\times radix=radix,转化为十进制等于radix，而这个radix需要等于N1的十进制数。$N1的量级在10^16次方上，所以待求的进制也需要用long long 来存，否则会爆int。

所以，这里不要误以为让求的进制也在36之内，这是错误的！！！ 待求进制数非常大，会爆int。

经过上面的分析，我们已经知道待求进制数 在1~$target$之间，枚举的区间比较大。

假设 k进制下4位数为：$(abcd{)}_k$，它表示的十进制是$s=a\times k^3+b\times k^2+c\times k+d$
当进制k变大的时候，这个数对应的十进制数是在变大的。 这是单调的！！！ 所以我们会想到 用二分法来加速枚举进制。

每次二分查找进制区间$[1,target]$的一个中点mid ，判断 mid进制下得到的十进制数 和 target的关系，如果小，则 在mid的右侧区间在二分查找；如果大了，则在mid的左侧区间继续查找进制。

这里的左边界是1不严谨，实际上进制数最小值应该是 N2中出现的数字的最大值+1. 比如N2 = 123 那么这个数的进制最小也是 3+1 =4进制。

所以，我们可以二分查找第一个大于等于target这个数的进制mid。如果这个数等于target说明有解，否则说明无解。

ac代码

#include<bits/stdc++.h> using namespace std;typedef long long LL;//0到z的字符表示：映射成 int型的 0 到35 整型数 int get(char c){if(c <= '9') return c-'0';return c-'a'+10; // a~z 映射到10~35 }// r进制转化为 十进制 LL calc(string a , LL r){LL res = 0;for(auto c: a){//如果计算出来的结果很大，大于long long 说明肯定无解,因为进制数不超过1e16//此时仅需要返回1个大的数即可if((double)res *r + get(c) > 1e16) return 1e18;res = res * r + get(c); //秦九韶算法 求十进制数}return res; }int main(){string n1,n2; //两个数cin>>n1>>n2;int tag ,radix; //进制cin>>tag >> radix;//目的是让n1已知，n2待求。if(tag==2) swap (n1 ,n2); LL target = calc(n1, radix); // 计算十进制下是多少//二分查找一个合适的进制LL l =1, r = target+1; //进制的最大值是target+1.//求进制的最小值for(auto c: n2) l =max(l , (LL)get(c)+1); while(l<r){LL mid = l +r >> 1;if(calc(n2,mid)>=target) r=mid;else l = mid +1;}//while退出的时候l ==r//大于等于target的第一个数 if(calc(n2, r)!=target){cout<<"Impossible";}else cout<<r<<endl;}

补充：

秦九韶算法 用来快速求其他进制转换为十进制的值是多少。

// r进制转化为 十进制 //a中存的是r进制数数值， r表示进制 LL calc(string a , LL r){LL res = 0;for(auto c: a){res = res * r + get(c); //秦九韶算法 求十进制数}return res; }

上面用到的get函数是用来将字符转变成数字，比如a变成10

//0到z的字符表示：映射成 int型的 0 到35 整型数 int get(char c){if(c <= '9') return c-'0';return c-'a'+10; // a~z 映射到10~35 }

来源：维基百科

比如m进制数abcd转换成十进制数是多少？

r=0; r= r*m +a; r= r*m+b; r=r*m+c; r=r*m+d; 可以用循环来写

十进制转化为其他进制：带余除法。

题目链接

PAT甲级1010 Radix

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的PAT甲级1010 Radix ：[C++题解]进制位、秦九韶算法、二分（PAT通过率最低的一道题0.11）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。