很长时间没做，忙于考研和实习，久违的的拾起了算法。做了很长时间，其实总体思路还是很简单的，但满分不知道为什么就是到不了，又因为网上很多答案包括柳神的都是c++，无法参透，姑且只能这样了。

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:

2

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossible

题目分析：

一方面，N1和N2的数字输入是不方便用int数组的，因该用字符串来分个存储，这样既方便又高效。另一方面，程序的整体流程就是：

1. 输入、存储。
2. 判断tag，到这大概能写出main函数，根据result变量确定输出数字还是“impossible”

   int main() {
        int result;
        scanf("%s %s %d%d",&N1,&N2, &tag, &radix);
            if (tag == 1)
            {
                result = Radix(N1, N2,radix );
            }
            else if(tag==2)
            {
                result = Radix(N2,N1,radix);
            }
            else
            {
                result = 0;
            }
   
        if (result != 0)
            printf("%d", result);
        else
            printf("Impossible");
       return 0;
    }　　
   

3. 编写具体的转换函数，结果返回到result。

个人想法：

主题函数很好写，而且不需要在意题目中提到的出现多个可转换的进制输出最小进制，当你第一次遍历得到正确进制数时就可以直接输出。

转换进制的函数Radix(char *tar,char *cha,int radix)，tar数组直接按照radix写一个for循环转换为二进制，cha则多加一个for循环进行多个进制的遍历，（这里注意的是，不是只到36就可以的，我相同的程序在只遍历36次时只有19分，遍历过多又会有超时，最高在999999次时达到24分），转换进制的代码就好写了。

 1 int Radix(char *tar,char *cha,int radix) {
 2     double sum1 = 0;
 3     for (int i = strlen(tar)-1; i >=0; i--)
 4     {
 5         double tmp;
 6         tmp = tar[i];
 7         if (tmp > '9')tmp = tmp - 'a' + 10;//a-z
 8         else if (tmp < 'a'&&tmp>='0')tmp -= '0';//0-9
 9         if (tmp >= radix) return 0;
10         sum1 += tmp * pow(radix,strlen(tar)-i-1);
11     }
12     for (int i = 0; i <= 999999;i++) {
13         double sum2 = 0;
14         for (int j = strlen(cha) - 1; j >= 0; j--) {
15             double tmp;
16             tmp = cha[j];
17             if (tmp > '9')tmp =tmp- 'a' + 10;//a-z
18             else if (tmp < 'a' && tmp >= '0')tmp -= '0';//0-9
19             if (tmp >= i) break;
20             sum2 += tmp * pow(i, strlen(cha) - j - 1);
21         }
22 
23         if (sum1 == sum2)return i;
24     }
25     return 0;
26 }

在多次调试时发现需要注意：

1. 输入N1和N2数组时， scanf(“%s %s %d%d”,&N1,&N2, &tag, &radix)；%s后面必须有空格，这样每个字符才会被分割到数组里面。
2. 求和变量sum2与sum1不同，需写在for循环内，不然遍历下一次时会sum2因为不会清0而不断累加导致一直报错。
3. sizeof（）求出来整个数组的长度，而strlen()求出有效长度。eg：110存入a[10]，sizeof(a)=10.strlen(a)=3
4. ‘110’在数组里面的位置是0，1，2，机器看起来就是‘011’，反过来了，在求和时要反过来
5. 输入的数字大于当前进制是不可能的，所以直接退出或break就好（9和19行）

最后得到的整体代码为：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #define _CRT_SECURE_NO_WARNINGS
 5 char N1[10],  N2[10];
 6 int tag, radix;
 7 int Radix(char* tar, char* cha, int radix);
 8  int main() {
 9      int result;
10      
11      scanf("%s %s %d%d",&N1,&N2, &tag, &radix);
12          if (tag == 1)
13          {
14              result = Radix(N1, N2,radix );
15          }
16          else if(tag==2)
17          {
18              result = Radix(N2,N1,radix);
19          }
20          else
21          {
22              result = 0;
23          }
24 
25      if (result != 0)
26          printf("%d", result);
27      else
28          printf("Impossible");
29     return 0;
30  }
31 int Radix(char *tar,char *cha,int radix) {
32     double sum1 = 0;
33     for (int i = strlen(tar)-1; i >=0; i--)
34     {
35         double tmp;
36         tmp = tar[i];
37         if (tmp > '9')tmp = tmp - 'a' + 10;//a-z
38         else if (tmp < 'a'&&tmp>='0')tmp -= '0';//0-9
39         if (tmp >= radix) return 0;
40         sum1 += tmp * pow(radix,strlen(tar)-i-1);
41     }
42     for (int i = 0; i <= 999999;i++) {
43         double sum2 = 0;
44         for (int j = strlen(cha) - 1; j >= 0; j--) {
45             double tmp;
46             tmp = cha[j];
47             if (tmp > '9')tmp =tmp- 'a' + 10;//a-z
48             else if (tmp < 'a' && tmp >= '0')tmp -= '0';//0-9
49             if (tmp >= i) break;
50             sum2 += tmp * pow(i, strlen(cha) - j - 1);
51         }
52 
53         if (sum1 == sum2)return i;
54     }
55     return 0;
56 }

View Code

结果：