点击链接PAT甲级-AC全解汇总

题目：
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
1

Sample Output 1:

2
1

Sample Input 2:

1 ab 1 2
1

Sample Output 2:

Impossible
1

题意：

注意：
对于case7 进制数很大的情况我的思路：
因为：$(数字首位+1)\ast radi{x}^{数字长度}>a$
那么：$radix>\sqrt[数字长度]{\frac{a}{数字首位+1}}$
后来！！！： 我发现，case直接输出a就行了…???
公式都没派上用场！

我的代码：

#include
using namespace std;

long long  string_to_int_withRADIX(string str,int radix,long long cmp=-1)
{
    long long  sum=0;
    reverse(str.begin(),str.end());
    for(int i=0;i<str.length();i++)
    {
        long long  num;
        if(str[i]>='0'&&str[i]<='9')num=str[i]-'0';
        else num=str[i]-'a'+10;
        //乘权相加
        if(cmp!=-1&&num>=radix)return -1;//continue
        sum+=num*pow(radix,i);
        if(cmp!=-1&&str.length()==1&&sum!=cmp)return -2;//impossible
        if(cmp!=-1&&sum>cmp)return -2;//impossible
    }
    if(cmp!=-1&&sum==cmp)return-3;//same
    else if(cmp!=-1)return -1;//continue

    return sum;//计算a
}

int main()
{
    string str1,str2,b;
    long long tag,radix_tag,a;
    cin>>str1>>str2>>tag>>radix_tag;

    if(tag==1)
    {
        a=string_to_int_withRADIX(str1,radix_tag);
        b=str2;
    }
    else
    {
        a=string_to_int_withRADIX(str2,radix_tag);
        b=str1;
    }

    int radix=2;

    //公式推导
    int b_0=(b[0]>='0'&&b[0]<='9')?(b[0]-'0'):(b[0]-'a'+10);
    if(b.length()>1)radix=pow((1.0*a/(b_0+1)),double(1/(b.length()-1)));

    while(radix<1000)
    {
        int flag=string_to_int_withRADIX(b,radix,a);
        if(flag==-1)radix++;
        else if(flag==-2){cout<<"Impossible";return 0;}
        else if(flag==-3){cout<<radix;return 0;}
    }
    cout<<a<<endl;//case 7
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

希望各位独立思考解题办法，就算想不出来看的别人AC代码，也是抱着学习的心态，而不是为了完成任务还复制粘贴发原创的文章。