{"id":476,"date":"2020-01-12T16:45:15","date_gmt":"2020-01-12T08:45:15","guid":{"rendered":"http:\/\/www.guanhaobo.cn\/?p=476"},"modified":"2020-01-12T16:45:15","modified_gmt":"2020-01-12T08:45:15","slug":"pat-advanced-level-practice-1010-radix","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=476","title":{"rendered":"PAT (Advanced Level) Practice 1010 Radix"},"content":{"rendered":"

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.<\/p>\n

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.<\/p>\n

Input Specification:<\/h3>\n

Each input file contains one test case. Each case occupies a line which contains 4 positive integers:
\nN1 N2 tag radix<\/code>
\nHere 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.<\/p>\n

Output Specification:<\/h3>\n

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.<\/p>\n

Sample Input 1:<\/h3>\n
6 110 1 10\n<\/code><\/pre>\n
Sample Output 1:<\/h3>\n
2\n<\/code><\/pre>\n
Sample Input 2:<\/h3>\n
1 ab 1 2\n<\/code><\/pre>\n
Sample Output 2:<\/h3>\n
Impossible\n<\/code><\/pre>\n
\u9898\u76ee\u5927\u610f<\/h3>\n
\u7ed9\u51fa\u4e24\u4e2a\u6570\u5b57N1,N2\uff0c\u4e0d\u8d85\u8fc710\u4f4d\uff0c\u4ee5 0-9 \u8868\u793a 0-9\uff0c a-z \u8868\u793a 10-35\u3002\u5df2\u77e5\u5176\u4e2d\u4e00\u4e2a\u6570\u7684\u8fdb\u5236\u4e3aradix\uff0ctag\u4e3a1\u8868\u793a\u7b2c\u4e00\u4e2a\u6570\uff0ctag\u4e3a2\u8868\u793a\u7b2c\u4e8c\u4e2a\u6570\u3002\u6c42\u53e6\u4e00\u4e2a\u6570\u7684\u8fdb\u5236\u4e3a\u591a\u5c11\uff0c\u53ef\u4ee5\u8ba9N1\u4e0eN2\u76f8\u7b49\uff0c\u5982\u679c\u6709\u591a\u4e2a\u7b54\u6848\u8f93\u51fa\u6700\u5c0f\u7684\u3002<\/p>\n
\u9898\u76ee\u5206\u6790<\/h3>\n
\u5047\u8bbetag\u4e3a1\uff0c\u5373\u5df2\u77e5N1\u7684\u8fdb\u5236\u4e3aradix\u3002
\n\u5f88\u591a\u4eba\u770b\u5230\u8fd9\u9053\u9898\u8ba4\u4e3a\u76f4\u63a5\u4ece2\u8fdb\u5236\u679a\u4e3e\u523036\u8fdb\u5236\u5c31\u884c\u4e86\uff0c\u4f46\u5b9e\u9645\u4e0a\u9898\u76ee\u4e2d\u5e76\u6ca1\u6709\u9650\u5236\u6700\u5927\u662f36\u8fdb\u5236\uff0c\u9898\u76ee\u53ea\u662f\u9650\u5236\u4e86\u6bcf\u4e00\u4f4d\u4e0a\u7684\u6570\u5b57\u6700\u5927\u4e3a z \u4e5f\u5c31\u662f35\uff0c\u4e5f\u5c31\u662f\u8bf4\u6570\u5b57zzz<\/code>\u53ef\u4ee5\u662f100\u8fdb\u5236\u4e5f\u53ef\u4ee5\u662f1000\u8fdb\u5236\uff0c\u53ea\u8981\u5927\u4e8e35\u5373\u53ef\u3002
\n\u7531\u4e8e\u53ef\u80fd\u7684\u8fdb\u5236\u8303\u56f4\u592a\u5927\uff0c\u4e00\u4e00\u679a\u4e3e\u80af\u5b9a\u4f1a\u8d85\u65f6\uff0c\u6240\u4ee5\u6211\u4eec\u9700\u8981\u4f7f\u7528\u4e8c\u5206\u67e5\u627e\u3002
\n\u4e8c\u5206\u67e5\u627e\u7684\u5de6\u8fb9\u754c\u662f\u4ec0\u4e48\u5462\uff1f
\n\u5bf9\u4e8e\u4e00\u4e2a\u6570\uff0c\u5b83\u7684\u8fdb\u5236\u6570\u6700\u5c0f\u503c\u4e3amax(2 , (\u6bcf\u4e2a\u6570\u4f4d\u4e0a\u6700\u5927\u7684\u6570 + 1))<\/code>\uff0c\u6bd4\u59821a<\/code>\u8fd9\u4e2a\u6570\uff0c\u6700\u5c0f\u8fdb\u5236\u4e3a11\u8fdb\u5236\uff0ca+1=11<\/code>\u3002\u8fd9\u5c31\u662f\u4e8c\u5206\u67e5\u627e\u7684\u5de6\u8fb9\u754c\u3002
\n\u90a3\u4e48\u4e8c\u5206\u67e5\u627e\u7684\u53f3\u8fb9\u754c\u662f\u4ec0\u4e48\u5462\uff1f
\n\u5982\u679cN2\u957f\u5ea6\u4e3a1\uff0c\u90a3\u4e48\u5b83\u7684\u8fdb\u5236\u53ea\u8981\u5927\u4e8e\u7b49\u4e8emax(2 , N2 + 1))<\/code>\u7ed3\u679c\u90fd\u662f\u76f8\u540c\u7684\u3002\u56e0\u6b64N2\u957f\u5ea6\u4e3a1\u65f6\u4e0d\u5fc5\u8fdb\u884c\u4e8c\u5206\u67e5\u627e\uff0c\u76f4\u63a5\u6309\u7167\u8fdb\u5236\u4e3amax(2 , N2 + 1))<\/code>\u6765\u8ba1\u7b97\u5373\u53ef\u3002
\n\u5982\u679cN2\u957f\u5ea6\u5927\u4e8e1\uff0c\u90a3\u4e48\u8fd9\u65f6 N2 \u7684\u5012\u6570\u7b2c\u4e8c\u4f4d\u6700\u5c0f\u662f1\uff0c\u8fd9\u65f6\u5b83\u7684\u8fdb\u5236\u53ea\u8981\u7b49\u4e8eN1 + 1<\/code> \u5c31\u6709 N2 > N1<\/code>\uff0c\u6240\u4ee5\u6bd4N1<\/code>\u66f4\u5927\u7684\u8fdb\u5236\u5c31\u4e0d\u7528\u8003\u8651\u4e86\u3002\u8fd9\u5c31\u662f\u4e8c\u5206\u67e5\u627e\u7684\u53f3\u8fb9\u754c\u3002
\n\u7efc\u4e0a\u6240\u8ff0\uff0c\u5206\u4e24\u7c7b\u60c5\u51b5\u3002
\nN2\u957f\u5ea6\u7b49\u4e8e1\u65f6\uff0c\u76f4\u63a5\u5224\u65adN2\u662f\u5426\u548cN1\u76f8\u7b49\uff0c\u5982\u679c\u76f8\u7b49\u5219\u7b54\u6848\u4e3amax(2 , N2 + 1))<\/code>\uff0c\u4e0d\u76f8\u7b49\u5219\u4e3aImpossible<\/code>\u3002
\nN2\u957f\u5ea6\u5927\u4e8e1\u65f6\uff0c\u4e8c\u5206\u67e5\u627eN2\u7684\u8fdb\u5236\uff0c\u8303\u56f4\u662f[max(2 , (\u6bcf\u4e2a\u6570\u4f4d\u4e0a\u6700\u5927\u7684\u6570 + 1)), N1]<\/code>\u3002
\n\u5f53\u7136\uff0c\u4e5f\u53ef\u4ee5\u4e0d\u5206\u4e24\u79cd\u60c5\u51b5\uff0c\u76f4\u63a5\u5728\u4e8c\u5206\u5230\u7b54\u6848\u65f6\u4ee4right = mid - 1<\/code>\u7136\u540e\u7ee7\u7eed\u5bfb\u627e\u7b54\u6848\uff0c\u76f8\u5f53\u4e8e\u628a\u957f\u5ea6\u7b49\u4e8e1\u65f6\u51fa\u73b0\u65e0\u7a77\u89e3\u7684\u60c5\u51b5\u5305\u542b\u4e86\u3002
\n\u6ce8\u610f\u4e8b\u9879\uff1a\u6570\u636e\u8303\u56f4\u7528 int \u662f\u4e0d\u884c\u7684\uff1b\u4e8c\u5206\u65f6\u4f1a\u51fa\u73b0\u8d1f\u6570\u7684\u60c5\u51b5\uff0c\u51fa\u73b0\u8d1f\u6570\u8bf4\u660e\u6570\u5b57\u592a\u5927\u6ea2\u51fa\u4e86\u3002<\/p>\n
AC\u4ee3\u7801<\/h3>\n
#include <bits\/stdc++.h>\nusing namespace std;\nlong long f(string s, long long radix) \/\/\u5c06radix\u8fdb\u5236\u7684\u6570\u8f6c\u4e3a10\u8fdb\u5236\n{\n    long long ans = 0;\n    for (int i = s.length() - 1; i >= 0; i--)\n    {\n        int temp = (s[i] <= '9' && s[i] >= '0') ? (s[i] - '0') : (s[i] - 'a' + 10);\n        ans += temp * pow(radix, s.length() - i - 1);\n    }\n    return ans;\n}\nint main()\n{\n    string n1, n2;\n    int tag, radix, i, ans = 1 << 30;\n    long long num1, num2;\n    cin >> n1 >> n2 >> tag >> radix;\n    \/\/\u4ea4\u6362\uff0c\u8f6c\u6362\u4e3a\u5df2\u77e5n1\u7684\u8fdb\u5236\uff0c\u6c42n2\u8fdb\u5236\n    if (tag == 2)\n        swap(n1, n2);\n    \/\/\u5c06n1\u8ba1\u7b97\u4e3a10\u8fdb\u5236\u8d4b\u7ed9num1\n    num1 = f(n1, radix);\n    if (n2.length() == 1) \/\/\u53ea\u6709\u957f\u5ea6\u4e3a1\u624d\u6709\u53ef\u80fd\u51fa\u73b0\u591a\u79cd\u7b54\u6848\n    {\n        int value = (n2[0] <= '9' && n2[0] >= '0') ? (n2[0] - '0') : (n2[0] - 'a' + 10);\n        if (value == num1)\n            cout << max(2, value + 1) << endl;\n        else\n            cout << \"Impossible\" << endl;\n    }\n    else\n    {\n        \/\/\u627e\u51fan2\u4e2d\u6700\u5927\u7684\u6570\uff0c\u52a0\u4e00\u5373\u4e3a\u6700\u5c0f\u53ef\u80fd\u7684\u8fdb\u5236\n        char maxch = '0';\n        for (i = 0; i < n2.length(); i++)\n            maxch = max(maxch, n2[i]);\n        int begin = (maxch <= '9' && maxch >= '0') ? (maxch - '0') : (maxch - 'a' + 10);\n        \/\/\u4e8c\u5206\u67e5\u627en2\u7684\u8fdb\u5236\n        long long left = max(2, begin + 1), right = num1 + 1; \/\/n2\u5012\u6570\u7b2c\u4e8c\u4f4d\u81f3\u5c11\u662f1\uff0c\u5df2\u7ecf\u5927\u4e8enum1\u4e86\uff0c\u6240\u4ee5\u8fdb\u5236\u6570\u6700\u5927\u4e3anum1+1\n        while (left <= right)\n        {\n            long long mid = left + (right - left) \/ 2;\n            num2 = f(n2, mid);\n            if (num1 == num2)\n            {\n                ans = mid;\n                break;\n            }\n            else if (num1 < num2 || num2 < 0) \/\/\u6570\u592a\u5927\u6ea2\u51fa\u4e86\n                right = mid - 1;\n            else\n                left = mid + 1;\n        }\n        if (ans == 1 << 30)\n            cout << \"Impossible\" << endl;\n        else\n            cout << ans << endl;\n    }\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
Given a pair of positive integers, for example, 6 and 1 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[23,32],"class_list":["post-476","post","type-post","status-publish","format-standard","hentry","category-algo","tag-pat","tag-32"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/476","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=476"}],"version-history":[{"count":0,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/476\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=476"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=476"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=476"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}