B1010 Radix (25分)
-
Each case occupies a line which contains 4 positive integers:
不用考虑为0的情况 -
Here N1 and N2 each has no more than 10 digits.
十位int会超,所以使用long long,但是long long在进行进制转换时还是会超,题中没有给出转换进制大小,所以要进行越界判断(第一处) -
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.
基数的范围为2~35,2~∞?,和35没半毛钱关系
最小基数:A digit is less than its radix
所以是最大位数+1
最大基数:N2是一位数或两位数,一位数时,要满足上述最小基数的情况,两位数要满足不能超过N1的十进制数。
- 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.
这题来说二分查找结果唯一的吧(・∀・(・∀・(・∀・*)
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;
const int MAX=10001;
const int INF=0x3f3f3f3f;
ll mp[MAX];
void init()
{
for(char c='0';c<='9';c++)
mp[c]=c-'0';
for(char c='a';c<='z';c++)
mp[c]=c-'a'+10;
}
ll getnum(string s,int radix)
{
ll ans=0;
for(int i=0;i<s.length();i++)
{
ans=ans*radix+mp[s[i]];
if(ans<0)
return -1;
}
return ans;
}
ll getlow(string s)
{
ll maxnum=0;
for(int i=0;i<s.length();i++)
{
if(maxnum<mp[s[i]])
maxnum=mp[s[i]];
}
return maxnum+1;
}
ll binary(ll low,ll high,string s,ll number)//ll number 开始为int 测试点10
{
while(low<=high)
{
ll mid=(low+high)/2;
ll result=getnum(s,mid);
if(result==number)
return mid;
else if(result>number||result==-1)
high=mid-1;
else if(result<number)
low=mid+1;
}
return -1;
}
int main()
{
string n1,n2;
int tag,radix;
cin>>n1>>n2;
scanf("%d%d",&tag,&radix);
init();
if(tag==2)
swap(n1,n2);
ll num1=getnum(n1,radix);
ll low=getlow(n2);//最小基数
ll high=max(num1,low);//最大基数//测试点0
ll ans=binary(low,high,n2,num1);
if(ans!=-1)
printf("%lld\n",ans);
else
printf("Impossible\n");
return 0;
}
网友评论