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 N_1 N1?? and N 2 N_2 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 Input1:
6 110 1 10
Sample Output1:
2
Sample Input2:
1 ab 1 2
Sample Output2:
Impossible
思路
- 二分思路借鉴柳神
- 注意由于没有给出
radix有多大,涉及整型的部分均需要使用long long - 使用二分法在有序的序列上查找需要的
radix, 不使用二分法将有一个点超时 - 二分法右端点是
max(r,num),防止num过小的情况
AC code
#include<iostream>
#include<cctype>
#include<algorithm>
using namespace std;
using ll = long long;ll cal(string& s,ll radix){
ll res=0,n=1;for(auto& x:s){
int digit = isdigit(x)?x-'0':x-'a'+10;res+=digit*n;n*=radix;}return res;
}ll search(string& s,ll num){
auto it = max_element(s.begin(),s.end());ll l = isdigit(*it)?*it-'0'+1:*it-'a'+11;ll r = max(num,l);if(num==0) return 1;while(l<=r){
ll mid = (l+r)/2;ll sum=cal(s,mid); if(sum>num or sum<0) r = mid-1; //超过了long long 的范围else if(sum==num) return mid;else l = mid+1;}return -1;
}
int main(){
string n1,n2;ll tag,radix;cin>>n1>>n2>>tag>>radix;if(tag==2) swap(n1,n2);reverse(n1.begin(),n1.end());reverse(n2.begin(),n2.end());ll sum = cal(n1,radix);ll ans = search(n2,sum);if(ans>0) printf("%lld",ans);else printf("Impossible");return 0;
}