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.
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.
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.
6 110 1 10
2
1 ab 1 2
Impossible
给出N1和N2，并指定其中一者的进制，求一个使两数相等的进制。这里的进制数可能是0~N的任何一个数，并且由于进制越小，同一个字符串表示的数越小，该题可以采用二分查找的方式寻找答案。
//#include <bits/stdc++.h> // //using namespace std; // //long long convert(string &raw,int radix) //{ // int len=raw.length(); // long long ans=0,p=1; // for(int i=len-1;i>=0;i--) // { // int r=0; // if(raw[i]>=‘0‘&&raw[i]<=‘9‘) // r=raw[i]-‘0‘; // else if(raw[i]>=‘a‘&&raw[i]<=‘z‘) // r=raw[i]-‘a‘+10; // if(r>=radix)return -1; // ans+=r*p; // p*=radix; // } // return ans; //} //int main() //{ // string N1,N2; // int tag,radix; // cin>>N1>>N2>>tag>>radix; // if(tag==1) // { // long long tmp=convert(N1,radix); // int lradix=1,rradix=max((long long)32,tmp); // while(lradix<rradix-1) // { // int t2radix=(lradix+rradix)/2; // long long t2=convert(N2,t2radix); // if(t2<tmp) // { // lradix=t2radix; // }else if(t2>=tmp) // { // rradix=t2radix-1; // } // } // if(convert(N2,(lradix+rradix)/2+1)==tmp){cout<<(lradix+rradix)/2+1<<endl;return 0;} // cout<<"Impossible"<<endl; // }else if(tag==2) // { // long long tmp=convert(N2,radix); // int lradix=1,rradix=max((long long)32,tmp); // while(lradix<rradix-1) // { // int t2radix=(lradix+rradix)/2; // long long t2=convert(N1,t2radix); // if(t2<tmp) // { // lradix=t2radix; // }else if(t2>=tmp) // { // rradix=t2radix-1; // } // } // if(convert(N1,(lradix+rradix)/2+1)==tmp){cout<<(lradix+rradix)/2+1<<endl;return 0;} // cout<<"Impossible"<<endl; // } // return 0; //} #include <bits/stdc++.h> using namespace std; bool validate(long long radix,string &raw,long long cmp) { int len=raw.length(); long long ans=0,p=1; for(int i=len-1;i>=0;i--) { long long r=0; if(raw[i]>=‘0‘&&raw[i]<=‘9‘) r=raw[i]-‘0‘; else if(raw[i]>=‘a‘&&raw[i]<=‘z‘) r=raw[i]-‘a‘+10; if(r>=radix)return false; ans+=r*p; p*=radix; } return ans==cmp; } long long convert(string &raw,long long radix) { int len=raw.length(); long long ans=0,p=1; for(int i=len-1;i>=0;i--) { long long r=0; if(raw[i]>=‘0‘&&raw[i]<=‘9‘) r=raw[i]-‘0‘; else if(raw[i]>=‘a‘&&raw[i]<=‘z‘) r=raw[i]-‘a‘+10; //if(r>=radix)return -1; ans+=r*p; p*=radix; } return ans; } int main() { string N1,N2; int tag,radix; cin>>N1>>N2>>tag>>radix; string known=tag==1?N1:N2; string unknown=tag==1?N2:N1; long long tmp=convert(known,radix); int len=unknown.length(); long long digitmax=0; for(int i=0;i<len;i++) { digitmax=max(digitmax,1+(long long)((unknown[i]>=‘0‘&&unknown[i]<=‘9‘)?unknown[i]-‘0‘:unknown[i]-‘a‘+10)); } long long left=digitmax; long long right=max(digitmax,tmp); while(left<=right) { long long mid=(left+right)/2; long long t2=convert(unknown,mid); if(t2==tmp) { cout<<mid<<endl; return 0; }else if(t2<0||t2>tmp) { right=mid-1; }else{ left=mid+1; } } cout<<"Impossible"<<endl; return 0; }
原文：https://www.cnblogs.com/zest3k/p/11450583.html