本文共 2727 字，大约阅读时间需要 9 分钟。

1010 Radix （25 point(s)）

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.

Now for any pair of positive integers N​1​​ and N​2​​, your task is to find the radix of one number while that of the other is given.

Input Specification:

Each input file contains one test case. Each case occupies a line which contains 4 positive integers:

N1 N2 tag radix

Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.

Output Specification:

For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.

Sample Input 1:

6 110 1 10

Sample Output 1:

2

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossible

Experiential Summing-up

这一题是得好好说说，就不用英文啦.... 首先，这一题不能用普通的进制转换方法，AC的代码应该也是我学习别人的（去年就提交了，现在也忘了是学习谁的了- -|||），数据的存储方面，读入方式要以字符串读入，在将其转换为整型的数组时，就需要确定这个数的最小进制，就比如，如果数字里最大的是‘ z '，那么它的进制数就不可能小于36。

然后，知道了最小的进制数，还需要知道最大的进制数，设两个数为A和B，其中A已知进制数，那么将其转换为十进制数为Ax，那么最大的进制数为Ax和最小进制数中大的那一个，因为题目说了，如果解不唯一，输出基数最小的那一个。（要知道，题目可没说解的基数在2~36之间哈，基数的上限理论上可以是无穷大，因为题目没有规定） 这一题需要用二分法，否则会有一个测试点超时，这也是题目的又一个坑点，还有，数据的运算与存储都需要用long long型，因为给的数最多为10位，然后如果按35^10小于10^19所以可以用（但是题目确实没有规定基数的范围，可能是题目不严谨吧= =，又或者是我侥幸AC了- -） 还有，二分的时候要注意，当前进制转换为十进制的值sum小于0或者是大于Ax，都是基数过大，因为小于0，按常理来说不应该，但是，有可能是因为数过大溢出导致变成了负数。 暂时能想到的就这么多啦，我理解的也不是十分透彻，毕竟0.11的通过率可是甲级里面倒数第二低的，欢迎大佬评论交流~( •̀∀•́ ) 

Accepted Code

#include 
   
    #include 
    
     #include 
     
      #include 
      
       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){	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		{			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){	LL ans=0,p=1;	for(int i=0;i
       
        answer||res<0)			high=mid-1;		else			low=mid+1;	}	return -1;}int main(){	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;}
       
      
     
    
   

 

转载地址：https://meteorrain.blog.csdn.net/article/details/86531915 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！