C语言如何从拼接后的整数中还原原始两个数值 要求不使用数组低开销

前提说明 #

原拼接函数的逻辑是：计算刚好大于y的最小10的幂次pow，最终返回值为x * pow + y。仅凭借拼接结果无法得到唯一的x、y对，存在多解情况，例如拼接结果为123时，合法的输入对包括(0,123)、(1,23)、(12,3)。以下实现可以遍历输出所有合法的输入对，如果你有额外约束（例如已知y的位数），可以直接定位到唯一解。

实现思路 #

• 首先计算拼接结果res的最高位对应的10的幂次，作为遍历的上限
• 从10的1次幂开始遍历所有可能的pow值：
  1. 用res % pow得到候选y，res / pow得到候选x
  2. 验证该候选y在原拼接函数中计算得到的pow是否和当前遍历的pow一致，一致则为合法输入对
• 全程仅使用算术运算，无数组操作，时间复杂度为O(n)，n为res的十进制位数，开销极低

代码实现 #

#include <stdio.h>

// 遍历输出res对应的所有合法x、y对
void deconcatenate(unsigned res) {
    // 计算res的最高位对应的10的幂次
    unsigned max_pow = 10;
    while (res >= max_pow) {
        max_pow *= 10;
    }

    // 遍历所有可能的pow值
    for (unsigned pow = 10; pow <= max_pow; pow *= 10) {
        unsigned y_candidate = res % pow;
        // 计算y_candidate对应的原拼接函数的pow值
        unsigned expected_pow = 10;
        while(y_candidate >= expected_pow) {
            expected_pow *= 10;
        }
        // 验证匹配
        if (expected_pow == pow) {
            unsigned x_candidate = res / pow;
            printf("合法输入对：x=%u, y=%u\n", x_candidate, y_candidate);
        }
    }
}

// 如果已知y的位数，可以直接得到唯一解，性能更高
void deconcatenate_with_y_digits(unsigned res, int y_digits, unsigned *x, unsigned *y) {
    unsigned pow = 1;
    for(int i = 0; i < y_digits; i++) {
        pow *= 10;
    }
    *y = res % pow;
    *x = res / pow;
}

int main() {
    // 测试用例：原输入x=12，y=34，拼接结果为1234
    deconcatenate(1234);
    return 0;
}

代码说明 #

• 遍历所有合法解的实现不需要任何额外输入，即可输出所有符合原拼接逻辑的输入对
• 若已知y的十进制位数，可以直接调用第二个函数，时间复杂度为O(k)，k为y的位数，性能开销更低
• 全程无数组、字符串操作，所有计算都为基础算术运算，符合要求

内容的提问来源于stack exchange，提问作者Geeta Naik