題目：
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 N1 and 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 Input 1:
6 110 1 10
Sample Output 1:
2
Sample Input 2:
1 ab 1 2
Sample Output 2:
Impossible
解題思路：
題目本身并不是很難，假設(shè)給出了N1的進(jìn)制，可以先將N1轉(zhuǎn)化為十進(jìn)制，然后從(radix=2)開始以某種方式試探N2的進(jìn)制，最后使得N2在轉(zhuǎn)換為十進(jìn)制后與N1相等即可。只是這上面的坑有點多。
坑點：
1.需要注意，測試用例中給出的radix不一定小于等于36，而且本題中出現(xiàn)的數(shù)據(jù)都遠(yuǎn)超過int能保存的范圍，到目前為止個人覺得最好的辦法還是自己構(gòu)建一個類來保存數(shù)據(jù)。筆者是使用deque<int>來保存數(shù)據(jù)的，但畢竟不是自己單獨定義的類，導(dǎo)致編碼看起來很混亂。
（之后查看其他人的解題思路發(fā)現(xiàn)用long long就可以……所以大概是我多慮了）
2.除了數(shù)據(jù)過大之外，在查找目標(biāo)radix的過程中需要運用適當(dāng)?shù)姆椒?，不然會超時?？淳W(wǎng)絡(luò)上其他人的方法多為使用二分查找，在這里我感覺再對deque<int>定義除法運算太耗時了，便取巧定義了一個變量做“步長”——
第一次以1111111111為步長搜索，
第二次以111111111為步長搜索，
……
最后一次以1為步長搜索，
在步長為1時搜索必然能命中結(jié)果，若不命中，則說明不存在，打印Impossible。使用此方法，最后也不會超時。
3.需要考慮到的特殊情況：進(jìn)制數(shù)應(yīng)大于原數(shù)中的每一位；當(dāng)答案不唯一時，輸出最小的進(jìn)制數(shù)。即——
當(dāng)test case為10 50 1 10時應(yīng)輸出Impossible，而非2；
當(dāng)test case為3 3 1 10時應(yīng)輸出4，而不是其他數(shù)字。
代碼：
編譯器：C++(g++)
#include <iostream>
#include <string>
#include <deque>
using namespace std;
//數(shù)字轉(zhuǎn)換為deque<int>的形式
deque<int> atodeq(long long n)
{
deque<int> ret;
while(n!=0)
{
ret.push_front(n%10);
n/=10;
}
return ret;
}
//兩個deque<int>形式的數(shù)字相加
deque<int> sum(deque<int> s1,deque<int> s2)
{
if(s1.size()<s2.size())
{
swap(s1,s2);
}
int jinwei=0;
deque<int> ret;
while(!s2.empty())
{
ret.push_front((s1.back()+s2.back()+jinwei)%10);
jinwei=(s1.back()+s2.back()+jinwei)/10;
s1.pop_back();
s2.pop_back();
}
while(!s1.empty())
{
ret.push_front((s1.back()+jinwei)%10);
jinwei=(s1.back()+jinwei)/10;
s1.pop_back();
}
if(jinwei!=0)
{
ret.push_front(jinwei);
}
return ret;
}
//兩個deque<int>形式的數(shù)字相乘
deque<int> times(deque<int> s1,deque<int> s2)
{
int i=0;
deque<int> ret(1,0);
while(!s2.empty())
{
deque<int> tmp=s1;
int jinwei=0;
for(int j=tmp.size()-1;j>=0;--j)
{
int t=tmp[j];
tmp[j]=(t*s2.back()+jinwei)%10;
jinwei=(t*s2.back()+jinwei)/10;
}
if(jinwei!=0)
{
tmp.push_front(jinwei);
}
for(int j=0;j!=i;++j)
{
tmp.push_back(0);
}
++i;
ret=sum(ret,tmp);
s2.pop_back();
}
return ret;
}
//將str形式的radix進(jìn)制的數(shù)字轉(zhuǎn)換為10進(jìn)制的deque<int>的形式
deque<int> toDecimal(const string &str,long long radix)
{
deque<int> ret(1,0);
string num=str;
for(deque<int> i(1,1);!num.empty();i=times(i,atodeq(radix)))
{
int t;
if(num.back()>='0'&&num.back()<='9')
{
t=num.back()-'0';
}
else
{
t=num.back()-'a'+10;
}
ret=sum(ret,times(atodeq(t),i));
num.pop_back();
}
return ret;
}
deque<int> toDecimal(const string &str,deque<int> radix)
{
deque<int> ret(1,0);
string num=str;
for(deque<int> i(1,1);!num.empty();i=times(i,radix))
{
int t;
if(num.back()>='0'&&num.back()<='9')
{
t=num.back()-'0';
}
else
{
t=num.back()-'a'+10;
}
ret=sum(ret,times(atodeq(t),i));
num.pop_back();
}
return ret;
}
int main()
{
string n1,n2;
int tag;
long long radix;
cin>>n1>>n2>>tag>>radix;
//特殊情況：兩者都是個位數(shù)
if(1==n1.size()&&1==n2.size())
{
if(n1==n2)
{
if(n1.back()>='0'&&n1.back()<='9')
{
cout<<(n1.back()-'0'+1)<<endl;
}
else
{
cout<<(n1.back()-'a'+11)<<endl;
}
}
else
{
cout<<"Impossible"<<endl;
}
return 0;
}
//特殊情況：兩者相等（但不是個位數(shù)）
if(n1==n2)
{
cout<<radix<<endl;
return 0;
}
deque<int> num;
if(2==tag)
{
swap(n1,n2);
}
num=toDecimal(n1,radix);
//考慮最小進(jìn)制數(shù)應(yīng)大于每一位數(shù)的情況
int minRet=2;
for(auto it=n2.cbegin();it!=n2.cend();++it)
{
if(*it>='0'&&*it<='9')
{
minRet=((*it-'0'+1)>minRet?(*it-'0'+1):minRet);
}
else
{
minRet=((*it-'a'+11)>minRet?(*it-'a'+11):minRet);
}
}
if(n1.size()<n2.size()||(n1.size()==n2.size()&&n1<n2))
{
//進(jìn)制在2~radix
long long min=minRet,max=radix-1,ret=(min+max)/2;
while(1)
{
if(min>max)
{
//min>max說明沒有合適的進(jìn)制
cout<<"Impossible"<<endl;
return 0;
}
auto result=toDecimal(n2,ret);
if(result.size()<num.size()||(result.size()==num.size()&&result<num))
{
//小于則向后半?yún)^(qū)查找
min=ret+1;
ret=(min+max)/2;
}
else if(result.size()>num.size()||(result.size()==num.size()&&result>num))
{
//大于則向前半?yún)^(qū)查找
max=ret-1;
ret=(min+max)/2;
}
else
{
//等于則輸出
cout<<ret<<endl;
return 0;
}
}
}
else
{
//進(jìn)制>radix
deque<int> ret=atodeq((radix>minRet?radix:minRet)),pre=ret;
//考慮n2為個位數(shù)的情況
if(1==n2.size())
{
if(toDecimal(n2,ret)!=num)
{
cout<<"Impossible"<<endl;
return 0;
}
}
int increase=10; //步長
while(1)
{
auto result=toDecimal(n2,ret);
if(result==num)
{
for(auto it=ret.cbegin();it!=ret.cend();++it)
{
cout<<*it;
}
cout<<endl;
return 0;
}
else if(result.size()>num.size()||(result.size()==num.size()&&result>num))
{
//步長為1的時候必然會命中，否則就是Impossible
if(increase!=1)
{
--increase;
ret=pre;
}
else
{
cout<<"Impossible"<<endl;
return 0;
}
}
pre=ret;
ret=sum(ret,deque<int>(increase,1));
}
}
return 0;
}
