題目：
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
解題思路：
題目本身并不是很難，假設給出了N1的進制，可以先將N1轉化為十進制遣耍，然后從(radix=2)開始以某種方式試探N2的進制，最后使得N2在轉換為十進制后與N1相等即可崖蜜。只是這上面的坑有點多。
坑點：
1.需要注意烙肺，測試用例中給出的radix不一定小于等于36纳猪，而且本題中出現(xiàn)的數(shù)據(jù)都遠超過int能保存的范圍，到目前為止個人覺得最好的辦法還是自己構建一個類來保存數(shù)據(jù)桃笙。筆者是使用deque<int>來保存數(shù)據(jù)的氏堤，但畢竟不是自己單獨定義的類，導致編碼看起來很混亂搏明。
（之后查看其他人的解題思路發(fā)現(xiàn)用long long就可以……所以大概是我多慮了）
2.除了數(shù)據(jù)過大之外鼠锈，在查找目標radix的過程中需要運用適當?shù)姆椒ǎ蝗粫瑫r星著」喊剩看網絡上其他人的方法多為使用二分查找，在這里我感覺再對deque<int>定義除法運算太耗時了虚循，便取巧定義了一個變量做“步長”——
第一次以1111111111為步長搜索同欠，
第二次以111111111為步長搜索，
……
最后一次以1為步長搜索横缔，
在步長為1時搜索必然能命中結果铺遂，若不命中，則說明不存在茎刚，打印Impossible襟锐。使用此方法，最后也不會超時膛锭。
3.需要考慮到的特殊情況：進制數(shù)應大于原數(shù)中的每一位粮坞；當答案不唯一時蚊荣，輸出最小的進制數(shù)。即——
當test case為10 50 1 10時應輸出Impossible莫杈，而非2互例；
當test case為3 3 1 10時應輸出4，而不是其他數(shù)字姓迅。
代碼：
編譯器：C++(g++)
#include <iostream>
#include <string>
#include <deque>
using namespace std;
//數(shù)字轉換為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進制的數(shù)字轉換為10進制的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);
//考慮最小進制數(shù)應大于每一位數(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))
{
//進制在2~radix
long long min=minRet,max=radix-1,ret=(min+max)/2;
while(1)
{
if(min>max)
{
//min>max說明沒有合適的進制
cout<<"Impossible"<<endl;
return 0;
}
auto result=toDecimal(n2,ret);
if(result.size()<num.size()||(result.size()==num.size()&&result<num))
{
//小于則向后半區(qū)查找
min=ret+1;
ret=(min+max)/2;
}
else if(result.size()>num.size()||(result.size()==num.size()&&result>num))
{
//大于則向前半區(qū)查找
max=ret-1;
ret=(min+max)/2;
}
else
{
//等于則輸出
cout<<ret<<endl;
return 0;
}
}
}
else
{
//進制>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;
}
