【PAT 甲级】A1010 Radix (25分)

【版本一：暴力模拟，24分】
测试点七运行超时…改一下…

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
int cti(char c)						//char to int
{
	if(c>='0'&&c<='9') return c-'0';
	else return c-'a'+10;
}
LL convert(string s,int radix)		//convert the radix of s into 10
{
	LL sum=0;
	for(int i=0;i<s.size();i++)
	sum=sum*radix+cti(s[i]);
	return sum;
}
int main(void)
{
	int tag,radix,m=1;
	string n1,n2;
	LL base,present=-1;
	cin>>n1>>n2>>tag>>radix;
	if(tag==1) swap(n1,n2);		//the radix of n2 is given.
	base=convert(n2,radix);
	for(int i=0;i<n1.size();i++)
	if(cti(n1[i])>=m) m=cti(n1[i])+1;	// m is the minimum radix of n1
	while(present<base)
	{
		present=convert(n1,m);
		m++;
	}
	if(present==base) printf("%d",m-1);
	else printf("Impossible");
} 

【版本二：二分法，25分AC】
稀里糊涂，我也不懂为什么我不引入temp变量，测试点十九就会答案错误…

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
int cti(char c)						//char to int
{
	if(c>='0'&&c<='9') return c-'0';
	else return c-'a'+10;
}
LL convert(string s,LL radix)		//convert the radix of s into 10
{
	LL sum=0;
	for(int i=0;i<s.size();i++)
	sum=sum*radix+cti(s[i]);
	return sum;
}
int main(void)
{
	int tag,radix;
	string n1,n2;
	LL base,present=-1,m=1,temp;
	cin>>n1>>n2>>tag>>radix;
	if(tag==1) swap(n1,n2);		//the radix of n2 is given.
	base=convert(n2,radix);
	for(int i=0;i<n1.size();i++)
	if(cti(n1[i])>=m) m=cti(n1[i])+1;	// m is the minimum radix of n1
	while(present<base)
	{
		present=convert(n1,m);
		m*=2;
	}
	m/=2;
	temp=m/2;
	if(present==base)
	{
		printf("%lld",m);
		return 0;
	}
	while(present>base && m>temp)
	{ 
		present=convert(n1,m);
		m--;
	}
	if(present==base) printf("%lld",m+1);
	else printf("Impossible");
}