1010. Radix (25)

#include<iostream>
#include<cstring>
using namespace std;
long long Cal(char a)
{
 if (a >= '0'&&a <= '9')
  return a - '0';
 else
  return a - 'a' + 10;
}
long long NUM(char N[], long long radix)
{
 long long sum = 0;
 long long i;
 for (i = 0; i <strlen(N); i++)
 {
  sum = Cal(N[i]) + sum*radix;
  if (sum<0)
   return -1;  //sum值过大产生溢出
 }
 return sum;
}
long long MR(char N[])
{
 long long max = 0;
 for (long long i = 0; i < strlen(N); i++)
  if (Cal(N[i]) > max)max = Cal(N[i]);
 return max + 1;
}
int main()
{
 char N1[15], N2[15];
 int Tag;
 long long Radix;
 cin >> N1 >> N2 >> Tag >> Radix;
 if (Tag == 2)
 {
  char tmp[15];
  strcpy(tmp, N2);
  strcpy(N2, N1);
  strcpy(N1, tmp);
 }
 long long num1 = NUM(N1, Radix);
 long long right = num1 + 1;
 long long left = MR(N2);

 while (left <= right)
 {
  long long center = (left + right) / 2;
  if (NUM(N2, center) > num1 || NUM(N2, center) == -1)
   right = center - 1;
  else if (NUM(N2, center) < num1)
   left = center + 1;
  else
  {
   cout << center;
   return 0;
  }
 }
 cout << "Impossible";
 return 0;
}

考的二分查找，关键还是题目没读懂

二分查找的上下界是给了进制的数到另一个可能的最小进制（MR函数）之间

最需要注意的就是，进制转换之后的数可能越界，在NUM函数中sum小于零，这个测试点中有