1010. Radix (25)

「爱情、让人受尽委屈。」 2022-05-31 07:28 168阅读 0赞

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

--------------------

题目大意：

给定一对正整数，例如，6和110，这个等式6=110正确吗？答案是“正确”，如果6是一个十进制数110是一个二进制数。  
对于任意一对正整数N1和N2，你的任务是找到一个数字的基数，而另一个基数是给定的。  
输入规格：  
每一个输入文件包含一个测试用例。每个案例占一行包含4个正整数：  
N1 N2 tag radix  
这里N1和N2都不超过10位。一个数字小于他的基数，从\{0-9，a-z\}中选择，0-9代表十进制的数字0-9，a-z代表十进制的10-35.最有一个“基数”当tag是1的时候是N1的基数当tag是2时是N2的基数。  
输出规范：  
对于每个测试用例，在一行中打印另一个数字的基数，使等式N1=N2是正确的。如果这个方程是不可能的，那就打印“Impossible”。如果解不是唯一的，输出最小的可能的基数。

代码：

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    long long int change(char c)
    {
        if(c>='0'&&c<='9')
        {
            return (c-'0');
        }
        else
        {
            return (c-'a'+10);
        }
    }
    long long calculate_value(char a[],long long int radix)
    {
        long long int n=0;
        int i,p;
        for(i=0;i<strlen(a);i++)
        {
            n*=radix;
            n+=change(a[i]);
            if(n<0)
            {
                return -1;
            }
        }
        return n;
    }
    int main()
    {
        long long int radix,tag,sum,min_value,max_value,mildle,sum2;
        int i,j;
        char N1[15],N2[15],t[15];
        scanf("%s %s %lld %lld",N1,N2,&tag,&radix);
        //printf("%s %s %lld %lld\n",N1,N2,tag,radix);
        if(tag==2)
        {
            strcpy(t,N1);
            strcpy(N1,N2);
            strcpy(N2,t);
        }
        sum=calculate_value(N1,radix);
        min_value=0;
        for(i=0;i<strlen(N2);i++)
        {
            if(min_value<change(N2[i]))
            {
                min_value=change(N2[i])+1;
            }
        }
        max_value=sum+1;
        //printf("%lld %lld",min_value,max_value);
        while(min_value<=max_value)
        {
            mildle=(min_value+max_value)/2;
            sum2=calculate_value(N2,mildle);
            //printf("%lld %lld\n",sum,sum2);
            if(sum2==-1||sum2>sum)
            {
                max_value=mildle-1;
            }
            else if(sum2<sum)
            {
                min_value=mildle+1;
            }
            else if(sum2==sum)
            {
                printf("%lld",mildle);
                return 0;
            }
        }
        printf("Impossible");
        return 0;
    }