a + b

题目大意

使用三个集合的数生成三个数 $a$ , $b$ , $c$ ，满足 $a + b = c$。

题解思路

命题证明：若存在整数 $a,b,c < 10^9$ 满足 $a + b = c$，则至少存在一组解使得 $a,b,c < 100$

证明思路

1. 基于进位特性的范围收缩：通过分析加法运算中每一位的进位情况，将可能的解空间从 $10^9$ 量级逐步缩小至两位数范围。
2. 个位情况分类讨论：以个位加法是否进位作为突破口，分情况证明存在小范围解。
3. 两位数等式的普适性：利用“每一位都进位”的假设，将多位数问题转化为两位数问题。

详细证明过程

假设：存在三个整数 $a,b,c \in \mathbb{Z}$，满足 $a + b = c$ 且 $0 \leq a,b,c < 10^9$，其中 $a,b,c$ 由三个特定字符集构建。

1. 个位加法的基础分析
   由于 $a + b = c$，等式成立的必要条件是个位数字满足 $a_0 + b_0 \equiv c_0 \pmod{10}$（其中 $x_0$ 表示整数 $x$ 的个位数字）。

   • 情况一：个位无进位
     若 $a_0 + b_0 = c_0$ 且 $a_0 + b_0 < 10$，此时取 $a' = a_0, b' = b_0, c' = c_0$，显然 $a',b',c' < 10 < 100$，命题得证。
   • 情况二：个位有进位
     若 $a_0 + b_0 = c_0 + 10$（即向十位进位），此时需进一步分析十位数字的组合情况。

2. 基于进位条件的十位分析
   假设个位进位为 $1$，若字符集 $S_c$ 中不包含数字 $1$，则无法通过更高位的运算消除个位进位带来的影响，导致等式不成立。因此，若有解且个位进位，则 $1 \in S_c$ 是必要条件。

   • 此时，为使等式成立，十位数字需满足 $a_1 + b_1 + 1 = c_1$（其中 $x_1$ 表示整数 $x$ 的十位数字），等价于 $a_1 + b_1 = c_1 - 1$。若能找到满足此条件的 $a_1,b_1,c_1$，则可构造出两位数解 $a' = 10a_1 + a_0, b' = 10b_1 + b_0, c' = 10c_1 + c_0$，且 $a',b',c' < 100$。

3. 多位数问题向两位数的转化
   由于假设每一位加法均产生进位，对于任意长度的 $a,b,c$，其每一段连续两位的数字组合（首尾拼接）均需满足加法进位规则。因此，验证所有可能解的充分条件是验证所有两位数组合，即只需在 $0 \leq a,b,c < 100$ 的范围内寻找解。

结论

通过对个位进位情况的分类讨论，结合多位数进位的普遍规律，证明了若存在满足 $a + b = c$ 且 $a,b,c < 10^9$ 的整数解，则必然存在一组解使得 $a,b,c < 100$。此结论将解空间显著缩小，为后续算法设计提供了理论依据。

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
using i128 = __int128;

int main() {
    string a, b, c;
    cin >> a >> b >> c;
    auto check = [&](int x, string _x) {
        vector<int> vis(19);
        for (auto i: _x) {
            vis[i - '0'] = 1;
        }
        do {
            if (!vis[x % 10]) return false;
            x /= 10;
        } while (x);
        return true;
    };


    for (int i = 0; i <= 100; i++) {
        for (int j = 0; j <= 100; j++) {
            int k = i + j;
            if (check(i, a) && check(j, b) && check(k, c)) {
                cout << i << " " << j << " " << k << endl;
                return 0;
            }
        }
    }
    cout << "impossible" << endl;
}