1010 Radix (25分)（进制转换，二分法，溢出）

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int Maxn = 1001;
typedef long long LL;
LL INF=(1LL<<63)-1;
//此题数值较大，需要考虑溢出情况
LL getnum(char a) //将字符转换为数字
{
if(a<='9' && a>='0')
return a - '0';
else if(a<='z' && a>= 'a')
return a-'a' + 10;
}
LL demicalN(string a,LL rad,LL t) //转换为十进制数字
{
LL len = a.size();
LL ans = 0,r=1;
for(int i = len - 1;i>=0;i--)
{
ans = ans + getnum(a[i]) * r;
r*=rad;
if(ans<0 || ans > t)
//小于0则为溢出，结果一定大于t
return - 1;
}
return ans;
}
int cmp(string n2,LL t,LL rad) //对比n2的十进制数和n1十进制数字的大小
{
LL temp = demicalN(n2,rad,t);
if(temp < 0)
return 1;
else if(temp == t)
return 0;
else
return -1;
}
LL getleft(string n2)
//得到最大的最小进制数字（一定大于原本数字中最大的一个数字）
{
LL m = -1;
int len = n2.size();
for(int i = 0;i<len;i++)
{
if(m<getnum(n2[i]))
m = getnum(n2[i]);
}
return m+1;
}
void binaryS(string n2,LL t)
//用二分法寻找
{
LL temp,flag = 0;
LL l=getleft(n2),r=max(t,l) + 1; //最大的右边界为n1十进制的或者为左边界，然后加1！！
while(l<=r)
{
LL mid = l/2 + r/2;
//直接相加可能溢出，先除法再加法可以避免
int num = cmp(n2,t,mid);
if(num == 0)
{
printf("%d",mid);
flag = 1;
break;
}
else if(num == 1)
{
r = mid - 1;
}
else if(num == -1)
l = mid + 1;
}
if(flag == 0)
printf("Impossible");
}
int main()
{
freopen("1.txt","r",stdin);
string n1,n2;
LL tag,rad,t;
cin>>n1>>n2>>tag>>rad;
if(tag == 2) //如果标签是二就转换顺序，方便后面做题
{
string temp;
temp = n1;
n1 = n2;
n2 = temp;
}
t = demicalN(n1,rad,INF);
binaryS(n2,t);
return 0;
}

最后

以上就是欢呼烤鸡为你收集整理的1010 Radix (25分)（进制转换，二分法，溢出）的全部内容，希望文章能够帮你解决1010 Radix (25分)（进制转换，二分法，溢出）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。