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

題意：給出兩個數(shù)，求在已知其中一個數(shù)的進(jìn)制下，另外一個數(shù)最小進(jìn)制下兩個數(shù)相等。

解析：誤導(dǎo)信息：the set { 0-9,?a-z?} where 0-9 represent the decimal numbers 0-9, and?a-z?represent the decimal numbers 10-35.? 以為進(jìn)制最大也就36? 其實(shí)是可以無窮大。但是也不是，在測試數(shù)據(jù)中，超過long long就是溢出，則Impossible。可知一個個遍歷過去肯定不理想，超時。可以想到二分查找。之前一直在第七個測試點(diǎn)卡著 只有24分，現(xiàn)在終于明白，原來若存在進(jìn)制，這最大也就是da，因為超過da，不可能da==db。

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a)) int gcd(int a,int b){return b?gcd(b,a%b):a;}int main() {char a[15],b[15];int c[15];ll tag,radix,l,la;ll da=0,db=0;cin>>a>>b>>tag>>radix;if(tag==1){ll k=1;la=strlen(a);for(ll i=la-1; i>=0; i--){if(a[i]>='a'&&a[i]<='z'){da+=(a[i]-'a'+10)*k;}else da+=(a[i]-'0')*k;k*=radix;}l=strlen(b);for(ll i=l-1; i>=0; i--){if(b[i]>='a'&&b[i]<='z'){c[i]=b[i]-'a'+10;}else c[i]=b[i]-'0';}}if(tag==2){ll k=1;la=strlen(b);for(ll i=la-1; i>=0; i--){if(b[i]>='a'&&b[i]<='z'){da+=(b[i]-'a'+10)*k;}else da+=(b[i]-'0')*k;k*=radix;}l=strlen(a);for(int i=l-1; i>=0; i--){if(a[i]>='a'&&a[i]<='z'){c[i]=a[i]-'a'+10;}else c[i]=a[i]-'0';}}ll maxx=0;for(ll i=0; i<l; i++){if(c[i]>maxx)maxx=c[i];}ll left=maxx+1,right=da+1;//最大的進(jìn)制ll ans;int f=0;while(left<=right){ll mid=(left+right)/2;db=0;ll k=1;for(ll i=l-1; i>=0; i--){db+=c[i]*k;k*=mid;}if(da==db){ans=mid;f=1;right=mid-1;}else if(db<0||db>da){right=mid-1;}else if(db<da){left=mid+1;}}if(!f)cout<<"Impossible"<<endl;elsecout<<left<<endl;return 0; }

?

?

總結(jié)

以上是生活随笔為你收集整理的1010 Radix的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。