- 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 N?1?? and N?2??, 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
- // 本题关键是确定进制的上限, 可以有很大很大, 故而设为 long long 类型
- // 进制转换和二分查找法是本题的解决方法
- #include<stdio.h>
- #include<iostream>
- #include<string>
- using namespace std;
- // 字符转化为数字
- int charToInt(char ch)
- {
- int rs= 0;
- if(ch>= '0' && ch <= '9')
- {
- rs = ch - '0';
- }
- if(ch>= 'a' && ch <= 'z')
- {
- rs = ch - 'a' + 10;
- }
- return rs;
- }
- // 化为十进制数
- long long changeToDecimal(string s,long long radix)
- {
- long long result = 0;
- for(int i = 0;i <s.length();i++)
- {
- result = result*radix + charToInt(s[i]);
- }
- return result;
- }
- // 比较 n1 与 n2 在十进制下的大小, 此函数可避免运行超时
- int compare(long long n1, string n2, long long radix)
- {
- long long sum = 0;
- for (int i = 0; i < n2.length();i++)
- {
- sum = sum * radix + charToInt(n2[i]);
- if (sum> n1) // 重点, 避免运行超时
- {
- return 1;
- }
- }
- if (sum> n1)// n1 <n2
- {
- return 1;
- }
- else if (sum < n1) // n1> n2
- {
- return -1;
- }
- else // 相等
- {
- return 0;
- }
- }
- // 二分查找, 十进制数与未知进制数相等时的进制
- long long Binary_Search(long long n,string p)
- {
- //step1: 未知进制数的进制下界 (每个位置数字的最大值 + 1)
- // 进制上界 (数 d1 和数 b 最大符号代表的数的最大值加上 1,n > 最小进制时, 则为 n+1; 否则为最小进制, 可以设为 low+1)
- int max = 0;
- for(int i = 0;i <p.length();i++)// 从末位开始
- {
- if(max < charToInt(p[i])) // 不为空
- {
- max = charToInt(p[i]);
- }
- }
- long long low = (long long)max + 1;// 记录最小的进制;
- long long high;// 记录最大进制;
- if(n> low)
- {
- high = n + 1;
- }
- else
- {
- high = low + 1;
- }
- long long mid;// 中间数
- //step2: 二分查找
- while(low <high)
- {
- mid = (low + high)/2;
- if(compare(n,p,mid) == 0)//(n == changeToDecimal(p,mid))
- {
- return mid;
- }
- else if(compare(n,p,mid) == 1)//(n < changeToDecimal(p,mid))
- {
- high = mid; //while 中是 low <= high 时, 为 mid-1; 此处是 low < high; 但按照书中一模一样的写法, 只能得 24 分
- }
- else
- {
- low = mid; //while 中是 low <= high 时, 为 mid+1; 此处是 low < high
- }
- }
- return -1;
- }
- int main()
- {
- string N1,N2;
- int tag;
- long long radix;
- cin>> N1;
- cin>> N2;
- cin>> tag;
- cin>> radix;
- // 全部化为 10 进制比较
- long long d1,d2;//N1 和 N2 化为十进制的值
- if(tag == 1)
- {
- d1 = changeToDecimal(N1,radix);
- if(Binary_Search(d1,N2) == -1)
- {
- cout << "Impossible" << endl;
- }
- else
- {
- cout << Binary_Search(d1,N2) << endl;
- }
- }
- if(tag == 2)
- {
- d2 = changeToDecimal(N2,radix);
- if(Binary_Search(d2,N1) == -1)
- {
- cout << "Impossible" << endl;
- }
- else
- {
- cout << Binary_Search(d2,N1) << endl;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2759353.html