本文共 2984 字，大约阅读时间需要 9 分钟。
为了确定两个任意进制数是否在某个进制下相等，我们可以采用以下方法：
问题分析：给定两个字符串表示的数，分别为A和B，它们的进制分别为radix。我们需要找到一个进制r，使得A在r进制下的十进制值等于B在r进制下的十进制值。
转换函数：首先，我们需要将每个数转换为十进制。这个过程需要考虑数字符号的范围，例如a-z表示10到35的数字。
二分查找：为了高效地查找合适的r，我们可以使用二分查找。我们需要确定r的范围，通常是从2到max_digit + 1，其中max_digit是给定数中的最大数字。
比较函数：在每次二分查找中，我们需要一个函数来比较给定的r是否使得A和B相等。这个函数会将A和B转换为十进制并比较它们的值。
优化处理：为了避免溢出，我们使用长整数类型。同时，我们需要确保转换过程中的正确性和效率。
数据类型选择：使用long long类型来存储转换后的十进制数，避免溢出。
范围确定：确定二分搜索的范围，确保能够覆盖所有可能的r值。
转换函数优化：确保转换过程高效且正确，处理所有可能的数字符号。
错误处理：检查输入的数字符合规定的进制要求，避免无效输入导致的错误。
#include#include #include #include #include #include #include using namespace std;long long toDecimalCase(char *n, long long radix) { long long result = 0; long long length = strlen(n); long long m = 1; for (int i = length - 1; i >= 0; i--) { char c = n[i]; if (c >= 'a' && c <= 'z') { result += (c - 'a' + 10) * m; m *= radix; } else if (c >= '0' && c <= '9') { result += (c - '0') * m; m *= radix; } else { return -1; // 非法字符 } } return result;}long long findLowNum(char *n) { long long low = 0; long long length = strlen(n); for (int i = length - 1; i >= 0; i--) { char c = n[i]; if (c >= 'a' && c <= 'z') { low = max(low + 1, (c - 'a' + 10) + 1); } else if (c >= '0' && c <= '9') { low = max(low + 1, (c - '0') + 1); } } return low;}long long compare(long long newNum, char *n1, long long mid) { long long sum = 0; long long m = 1; for (int i = strlen(n1) - 1; i >= 0; i--) { char c = n1[i]; if (c >= 'a' && c <= 'z') { sum += (c - 'a' + 10) * m; m *= mid; } else if (c >= '0' && c <= '9') { sum += (c - '0') * m; m *= mid; } else { return -1; // 非法字符 } if (sum > newNum) { return 1; } } if (sum > newNum) { return 1; } else if (sum == newNum) { return 0; } else { return -1; }}long long binarySearch(char *n, long long low, long long high, long long newNum) { while (low <= high) { long long mid = (low + high) / 2; long long cmp = compare(newNum, n, mid); if (cmp == 1) { high = mid - 1; } else if (cmp == -1) { low = mid + 1; } else { return mid; } } return -1;}int main() { char n1[11], n2[11]; char *num1 = n1, *num2 = n2; int tag; long long radix; long long result; scanf("%s %s %d %s", n1, n2, &tag, num3); radix = atoi(num3); long long newNum, low, high; switch (tag) { case 1: newNum = toDecimalCase(n1, radix); low = findLowNum(n2); high = newNum + 1; break; case 2: newNum = toDecimalCase(n2, radix); low = findLowNum(n1); high = newNum + 1; break; } if (newNum == -1 || low == -1) { printf("Impossible"); return 0; } low = max(low, 2); high = min(high, newNum + 1); result = binarySearch((!num1 ? n1 : num2), low, high, newNum); if (result != -1 && result != 0) { printf("%ld\n", result); } else { printf("Impossible"); } return 0;}
转换函数：toDecimalCase将一个数转换为十进制，返回其值或-1表示错误。
查找最低数：findLowNum确定数中的最小可能值，用于二分查找的下界。
比较函数：compare比较两个数在给定进制下的十进制值，用于二分查找。
二分查找：binarySearch使用二分法查找合适的进制，使得两个数相等。
主函数：读取输入，根据情况调用相应的转换和查找函数，输出结果。
通过这种方法，我们可以高效地找到两个任意进制数在相同进制下的相等值，或者确定其不可能相等。
转载地址：http://slqfk.baihongyu.com/