1010 Radix (25 分)

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

Sample Output 1:

2

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossible

直接暴力很简单，（注意进制下界为最大元素值+1）。。。第七个点超时。。肯定要用二分。。试了几次，第七个点过了，其他点反而错了。。不写想了。。24分差不多了。  然而将过了第七个点的代码投机取巧特判后复制到原来代码上就全过了。。唉！还是浪费时间啊

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int toNum(char n){if(isalpha(n)) return n-'a'+10;return n-'0';
}
//转为10进制数 
ll toDec(string x,int base){ll ans=0,b=1;for(int i=x.length()-1;i>=0;i--){ans+=toNum(x[i])*b;b*=base;}return ans;
}
int main(){
//	freopen("in.txt","r",stdin);string a[3];int tag,radix,m;cin>>a[1]>>a[2]>>tag>>radix;ll val=toDec(a[tag],radix);//找出最大的数字  基数必须大于最大数字 string str=a[3-tag];sort(str.begin(),str.end());int start=toNum(str[str.length()-1])+1;//别忘记+1 bool flag=true;int i;for(i=start;;i++){ll temp=toDec(a[3-tag],i);if(val==temp) break;if(val<temp){flag=false;break;}}if(!flag) cout<<"Impossible";else cout<<i;return 0;
}

满分：r=3e9  取得很重要，太大了可能就不是最小的答案了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int toNum(char n){if(isalpha(n)) return n-'a'+10;return n-'0';
}
//转为10进制数 
ll toDec(string x,int base){ll ans=0,b=1;for(int i=x.length()-1;i>=0;i--){ans+=toNum(x[i])*b;b*=base;}return ans;
}
int main(){
//	freopen("in.txt","r",stdin);string a[3];int tag,radix,m;cin>>a[1]>>a[2]>>tag>>radix;ll val=toDec(a[tag],radix);//找出最大的数字  基数必须大于最大数字 string str=a[3-tag];sort(str.begin(),str.end());int start=toNum(str[str.length()-1])+1;//别忘记+1 bool flag=true;int i;for(i=start;;i++){ll temp=toDec(a[3-tag],i);if(val==temp) break;if(val<temp){flag=false;break;}if(i>999999){//a[tag]比较小   那么我进制数一定在 start到radix-1之间   不可能大于radix  玩意radix很大 此时只有二分了ll l=i+1,r=3e9;while(l<=r){//若存在则最终重合点可能正是mid，所以<=的=号不能丢 ll mid=(l+r)/2;ll temp=toDec(a[3-tag],mid);if(val==temp){cout<<mid;return 0;}else if(val<temp||temp<=0){r=mid-1;}else l=mid+1;}//中间没有输出 说明找不到结果了 cout<<"Impossible";return 0;}}if(!flag) cout<<"Impossible";else cout<<i;return 0;
}