首页 > 其他 > 详细

PAT 甲级 1010 Radix

时间:2020-11-06 14:13:45      阅读:19      评论:0      收藏:0      [点我收藏+]
技术分享图片
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
typedef long long LL;
struct bign
{
    int len;
    int d[30];
    bign()
    {
        len=0;
        memset(d,0,sizeof(d));
    }
};
bign change(char str[],int &q)//将读入的字符串每一位保存进结构体相同下标的int数组里,并确定最小进制(即数串长度+1)
{
    q=1;
    bign a;
    a.len=strlen(str);
    for(int i=a.len-1;i>=0;--i)
    {
        if(isdigit(str[i]))
        {
            a.d[a.len-1-i]=str[i]-0;

        }
        else
        {//将字母转换10进制,a-10,b-11。。。
            a.d[a.len-1-i]=str[i]-a+10;
        }
        q=q>a.d[a.len-1-i]?q:a.d[a.len-1-i];
    }
    ++q;
    return a;
}
LL transform(bign a,int r)//将r进制的数转化并返回10进制
{
    LL ans=0,p=1;
    for(int i=0;i<a.len;++i)
    {
        ans+=a.d[i]*p;
        p*=r;
    }
    return ans;
}
int binary_search(LL low,LL high,LL answer,bign a)
{
    while(low<=high)
    {
        LL mid=(low+high)/2;
        LL res=transform(a,mid);
        if(res==answer)
            return mid;
        else if(res>answer||res<0)
            high=mid-1;
        else
            low=mid+1;
    }
    return -1;
}

int main()
{//r1,r2分别代表对应数串最小进制
    int n,tag,radix,r1,r2;
    char a[20],b[20];
    scanf("%s %s %d %d",a,b,&tag,&radix);
    bign a1=change(a,r1);
    bign b1=change(b,r2);
    int ans;
    if(tag==1)
    {
        LL x=transform(a1,radix);
        LL l=r2;
        LL h=max(x,(LL)r2);
        ans=binary_search(l,h,x,b1);
    }
    else
    {
        LL x=transform(b1,radix);
        LL l=r1;
        LL h=max(x,(LL)r1);
        ans=binary_search(l,h,x,a1);
    }
    if(ans==-1)
        printf("Impossible\n");
    else
        printf("%d\n",ans);
    return 0;
}
View Code

转载https://blog.csdn.net/a845717607/article/details/86531915

PAT 甲级 1010 Radix

原文:https://www.cnblogs.com/jeseesmith/p/13936347.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!