PAT 甲级 1010 Radix (25 分) 一道很难得满分的题，很多坑，二分

落日映苍穹つ 2024-02-19 21:57 47阅读 0赞

1010 Radix (25 分)

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 N1 and N2, 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: ####

#### Sample Input 2: ####

1 ab 1 2

#### Sample Output 2: ####

Impossible

题目的大意是：给你两个数，N1和N2，给定其中一个数的基数，然后求另一个数的基数，使得两个数相等。

我第一个次暴力求解，而且没有注意基数的范围，只得了9分。

注意点：

1.进制的区间范围：我一开始以为2到36，其实并不是。 N2的下限通过找到其中最大的字符对应的数字minradix加1即可。而N2的上限不能直接等于N1+1，因为若N1等于0，那么上限值就为1，最小的进制为2进制。所以要先判断minradix是否大于N1的十进制值，若大于，则上限minradix+1，反之则N1的十进制+1

2 输入的N1/N2转化成十进制后可能超过Int的范围，要用long long 由于是用他们转化成十进制后的数作为上限，因此进制的上限值以及进制的中间值都可能会超过Int的范围。所以都要用long long

3 转化时可能存在溢出情况 由于进制的上限会非常大，在转化时就有可能会溢出，溢出后结果<0，所以若转化成十进制后<0，上限要缩小。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    #define LL long long
    LL to_ten(string s,LL r)    // 转化为10进制 
    {
    	LL cnt=0;
    	int len=s.length();
    	for(int i=0;i<len;i++)
    	{
    		if(s[i]<='9'&&s[i]>='0')
    		cnt=cnt*r+(s[i]-'0');
    		else
    		cnt=cnt*r+(s[i]-'a'+10);
        }
    	return cnt;
    }
    LL minr(string s)    // 找到最大的数字 
    {
    	LL r=0,m=0;
    	for(int i=0;i<s.size();i++)
    	{
    		if(s[i]<='9'&&s[i]>='0')
    		{
    			if(s[i]-'0'>m)
    			m=s[i]-'0';
    		}
    		else
    		{
    			if(s[i]-'a'+10>m)
    			m=s[i]-'a'+10;
    		}
    	}
    	return m+1;
    }
    int main()
    {
    	string t1,t2;
    	long long n1=0,n2=0,d=0,l,r,m;
    	int i,j,t,ra,f=0;
    	cin>>t1>>t2>>t>>ra;
    	if(t==1)
    	{
    		n1=to_ten(t1,ra);
    		l=minr(t2);        // 基数的下界 
    		r=max(r,n1)+1;     //基数的上界 
    //		cout<<r<<" "<<l<<endl;
    		while(l<=r)      // 开始二分 
    		{
    			
    			m=(l+r)/2;
    //			cout<<m<<endl;
    			n2=to_ten(t2,m);
    			if(n2==n1)
    			{
    				cout<<m<<endl;
    				break;
    			}
    			else
    			if(n2<0||n2>n1)   // n2小于0  是正+正溢出的情况 
    			r=m-1;
    			else
    			l=m+1;
    		}
    	}
    	else
    	{
    		n2=to_ten(t2,ra);
    		l=minr(t1);
    		r=max(r,n2)+1;
    //		cout<<r<<" "<<l<<endl;
    		while(l<=r)
    		{
    			m=(l+r)/2;
    			n1=to_ten(t1,m);
    			if(n2==n1)
    			{
    				cout<<m<<endl;
    				break;
    			}
    			else
    			if(n1<0||n2<n1)
    			r=m-1;
    			else
    			l=m+1;
    		}
    	}
    	if(l>r)
    	cout<<"Impossible"<<endl;
    	return 0;
    }