首页 > 代码库 > 1010. Radix (25)(进制 + 二分 + 模拟)
1010. Radix (25)(进制 + 二分 + 模拟)
Now for any pair of positive integers N1 and N2, 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 radixHere 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
Code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef unsigned long long LL; 5 6 char a[20], b[20], t[20]; 7 8 LL Trans(char s[], int e) 9 {10 int len = strlen(s);11 LL ans = 0;12 for (int i = 0; i < len; i++)13 {14 ans *= e;15 if (s[i] >= ‘0‘ && s[i] <= ‘9‘)16 ans += s[i] - ‘0‘;17 else18 ans += s[i] - ‘a‘ + 10;19 }20 return ans;21 }22 23 int main()24 {25 int tag, rad;26 scanf(" %s %s%d%d" , a , b , &tag , &rad);27 if (tag == 2)28 {29 strcpy(t, a);30 strcpy(a, b);31 strcpy(b, t);32 }33 LL an = Trans(a, rad);34 int bmax = 0;35 int blen = strlen(b);36 for (int i = 0; i < blen; i++)37 {38 if (b[i] >= ‘0‘ && b[i] <= ‘9‘)39 bmax = max(bmax, b[i] - ‘0‘);40 else41 bmax = max(bmax, b[i] - ‘a‘ + 10);42 }43 44 LL l = bmax + 1, r = an;45 while (l < r)46 {47 LL mid = l + r >> 1;48 LL amid = Trans(b, mid);49 if (amid == an)50 l = r = mid;51 else if (amid < an)52 l = mid + 1;53 else54 r = mid - 1;55 }56 57 if (Trans(b , l) == an)58 printf("%llu" , l);59 else60 printf("Impossible\n");61 return 0;62 }
1010. Radix (25)(进制 + 二分 + 模拟)