1010. Radix (25)

题目连接：https://www.patest.cn/contests/pat-a-practise/1010

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


这道题我一开始用的是常规的方法，从数字所有位的最大值加1开始依次累加计数，直到所得答案与给定Radix的数值相等。但是会有各种错误，勉强得到12分。代码如下：

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<string.h>
 4 #define Max 11
 5 char N[3][Max];
 6 int  digit(int tag)
 7 {
 8     int  cnt=0;
 9     while ((N[tag][cnt]>='0' && N[tag][cnt]<='9')||(N[tag][cnt]>='a' && N[tag][cnt]<='z'))
10     {
11         cnt++;
12     }
13     return cnt;
14 }
15 
16 
17 int main()
18 {
19 
20     long long n[3]={0};
21     int   i;
22     int  cnt[3];
23     int  tag,radix,other;
24     scanf("%s %s %d %d",&N[1],&N[2],&tag,&radix);
25 
26     if (tag==1)other=2;
27     else if (tag==2)other=1;
28     //printf("sdf")
29     cnt[tag]=digit(tag);
30     cnt[other]=digit(other);
31 
32     int Min=0;
33     for (i=0;i<cnt[other]-1;i++)
34     {
35         int num;
36         if (N[other][i]>='0'&&N[other][i]<='9')num=N[other][i]-'0';
37         else if (N[other][i]>='a'&&N[other][i]<='z')num=N[other][i]-'a'+10;
38         if (num>Min)Min=num;
39     }
40     //printf("%d %d
",cnt[tag],cnt[other]);
41     int  j=0;
42     for (i=cnt[tag]-1;i>=0;i--)
43     {
44         if (N[tag][i]>='0' && N[tag][i]<='9')n[tag]+=(pow(radix,i)*(N[tag][j++]-'0'));
45         else if (N[tag][i]>='a' && N[tag][i]<='z')n[tag]+=(pow(radix,i)*((N[tag][j++]-'a')+10));
46     }
47   //  printf("%lld
",n[tag]);
48 
49     int   answer=-1;
50     int   wei=Min+1;
51 
52     while (1)
53     {
54         j=0;
55         n[other]=0;
56         for (i=cnt[other]-1;i>=0;i--)
57         {
58             if (N[other][i]>='0' && N[other][i]<='9')n[other]+=(pow(wei,i)*(N[other][j++]-'0'));
59             else if (N[other][i]>='a' && N[other][i]<='z')n[other]+=(pow(wei,i)*((N[other][j++]-'a')+10));
60         }
61 
62         if (n[other]==n[tag])
63         {
64             answer=wei;
65             break;
66         }
67         else if (n[other]<n[tag])wei++;
68         else if (n[other]>n[tag])break;
69     }
70     if (answer==-1)printf("Impossible");
71     else if (answer>=1)printf("%lld",answer);
72     return 0;
73 }

View Code

然后，在网上参考了其他人的解法，他们说Radix和两个数值得设为long long 类型；还有就是得用二分查找，以避免超时。我参考了这位朋友(http://blog.csdn.net/matrix_reloaded/article/details/35880933)的代码又写了一遍，但最后还是有一个错误没找出来……希望大神能解答一下。代码如下：

#include<stdio.h>
#include<string.h>
char N[3][15];
long long int num1;

long long int First(long long int tag,long long int radix)
{
    long long int sum=0;
    long long int d=1;
    int cnt,i;
    cnt=strlen(N[tag]);//printf("%d
",cnt);
    for (i=cnt-1;i>=0;i--)
    {
        int num;
        if (N[tag][i]>='0'&& N[tag][i]<='9')num=N[tag][i]-'0';
        else num=N[tag][i]-'a'+10;
        sum=sum+num*d;
        d*=radix;
    }
    return sum;
}

 long long int Digit(long long int tag)
{
    int cnt,i;
    cnt=strlen(N[tag]);//printf("%d
",cnt);
    long long int min=-1;
    for (i=cnt-1;i>=0;i--)
    {
        int num;
        if (N[tag][i]>='0'&&N[tag][i]<='9')num=N[tag][i]-'0';
        else num=N[tag][i]-'a'+10;
        if (num>min)min=num;
    }
    return min+1;
}

int compare(long long int tag,long long int radix)
{
    long long int sum=0;
    int i,cnt;
    cnt=strlen(N[tag]);
    long long int d=1;
    for (i=cnt-1;i>=0;i--)
    {
        int num;
        if (N[tag][i]>='0'&&N[tag][i]<='9')num=N[tag][i]-'0';
        else num=N[tag][i]-'a'+10;
        sum=sum+num*d;
        if (sum>num1)return 1;
        d*=radix;
    }
        if (sum==num1)return 0;
        return -1;
}

long long int  BinarySearch(long long int tag )
{
    long long int L,R,M;
    L=Digit(tag);
    R=num1>L?num1:L;
    while(L<=R)
    {
        M=(L+R)/2;
        int res=compare(tag,M);
        if (res==1)R=M-1;
        else if (res==0)return M;
        else if (res==-1)L=M+1;
    }
    return -1;
}

int main()
{
    long long int tag,radix,other;
    long long int ans;
    scanf("%s %s %lld %lld",&N[1],&N[2],&tag,&radix);

    if (N[1]=="1"&& N[2]=="1"){printf("2");return 0;}
    if (N[1]==N[2]){printf("%d",radix);return 0;}

    num1=First(tag,radix);  //

    if (tag==1)other=2;
    else if (tag==2)other=1;

    ans=BinarySearch(other);

    if (ans==-1)printf("Impossible");
    else printf("%d",ans);

    return 0;
}