题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805507225665536
题意：给定n1、n2两个数，求可以是两者相等的进制；如果没有，输出Impossible
思路：
①暴力枚举进制数，超时/wa，错在样例7，这样写最多只能有24分。
盲猜样例7应该是这样的
input: output:
②开二分搜索进制数，转换出来的数会爆long long，所以二分的check要修改一下。
当要求的数只有一位时，不管是多少进制的数，算出来的答案都是一样的，so特判一下。
当要求的数大于一位时，答案如果存在，则唯一。
盲猜样例一应该是这样的
input: output:
tips：
①巧妙利用swap函数减少函数长度
②for()中不要用i<s.szie()或者i<strlen(s)，O(n)会变成O(n*n)
附上代码：
#include<bits/stdc++.h>
using namespace std;
const long long inf=(1ll<<)-;
long long cal(string s,long long radix)//计算s的radix进制数，转换成10进制数的值
{
long long ans=,rdixnum=;
int len=s.size();
for(int i=len-;i>=;i--)
{
if(s[i]>=''&&s[i]<='')ans+=1ll*(s[i]-'')*rdixnum;
else ans+=1ll*(s[i]-'a'+)*rdixnum;
rdixnum*=radix;
}
return ans;
} int main()
{
string s1,s2;
int tag,len1,len2;
long long ansnum=,radixnum=,ans=-,radix;
cin>>s1>>s2>>tag>>radix; if(tag==)swap(s1,s2);//交换
len1=s1.size();
len2=s2.size(); for(int i=len1-;i>=;i--)
{
if(s1[i]>=''&&s1[i]<='')ansnum+=1ll*(s1[i]-'')*radixnum;//计算已给数的十进制数值
else ansnum+=1ll*(s1[i]-'a'+)*radixnum;
radixnum*=radix;
}
long long l=,r=inf;
for(int i=;i<len2;i++)
{
if(s2[i]>=''&&s2[i]<='')l=max(l,s2[i]-''+1ll);//计算满足字母、数字要求的最小进制
else l=max(l,s2[i]-'a'+11ll);
}
if(len2==)
{
if(ansnum==cal(s2,l))cout<<l<<endl;
else cout<<"Impossible"<<endl;
}
else
{
while(l<=r)
{
long long mid=l+r>>1ll;
if(cal(s2,mid)==ansnum)
{
cout<<mid<<endl;
return ;
}
else if(cal(s2,mid)>ansnum||cal(s2,mid)<)r=mid-;//修改二分
else l=mid+;
}
cout<<"Impossible"<<endl;
}
return ;
}
我还是太难♂了
/(ㄒoㄒ)/~~