pat 甲级 A1010 Radix (25分)

题目链接：

https://pintia.cn/problem-sets/994805342720868352/problems/994805507225665536

 

题目分析：

二分查找。给定两个数，其中指出一个数的基数，判断是否存在对应的基数使得两个数相等。在查找基数时，应使用二分查找（不能采用顺序查找，否则会超时），且基数最大即为已知基数的那个数转十进制后，加一，基数最小记为该数中出现的最大系数加一。

 

 

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
char n1[20], n2[20], tmp[20];
ll sum1, sum2, r, temp , len, mid, ans = -1;
int tag;
ll pow1(char s[], ll r){
    ll sum = 0;
    for(int i = strlen(s)-1; i >= 0; i--){
        if('0' <= s[i] && s[i] <= '9') temp = s[i]-'0';
        else temp = s[i]-'a'+10;
        sum += temp*pow(r, strlen(s)-1-i);
    }
    return sum;
}
int main() {
    cin >> n1 >> n2 >> tag >>r ;
    if(tag == 2){
        strcpy(tmp, n1);
        strcpy(n1, n2);
        strcpy(n2, tmp);
    }
    sum1 = pow1(n1, r);
    for(int i=strlen(n2)-1;i>=0;i--){ //确定n2的最小可能基底
        if(n2[i] >= 'a' && n2[i] <= 'z') temp = n2[i] - 'a' + 10;
        else if(n2[i] >= '0' && n2[i] <= '9') temp=n2[i]-'0';
        if(temp>len) len=temp;
    }
    len = len + 1;   //最小可能基数
    r = sum1 + 1;    //最大可能基数
    while(len <= r ){        //二分法查找正确的基底
        mid = (len + r)/2;
        sum2 = pow1(n2, mid);
        if(sum1 == sum2) ans = mid;
        //基底过大，导致溢出
        if(sum2 >= sum1 || sum2 < 0) r = mid - 1;
        else len = mid + 1;
    }
    if(ans == -1) printf("Impossible\n");
    else printf("%ld\n",ans);
    return 0;
}