A + B
题目大意
使用三个集合的数生成三个数 aaa , bbb , ccc ，满足 a+b=ca + b = ca+b=c。
题解思路
命题证明：若存在整数 A,B,C<109A,B,C < 10^9A,B,C<109 满足 A+B=CA + B = CA+B=C，则至少存在一组解使得 A,B,C<100A,B,C < 100A,B,C<100
证明思路
1. 基于进位特性的范围收缩：通过分析加法运算中每一位的进位情况，将可能的解空间从 10910^9109 量级逐步缩小至两位数范围。
2. 个位情况分类讨论：以个位加法是否进位作为突破口，分情况证明存在小范围解。
3. 两位数等式的普适性：利用“每一位都进位”的假设，将多位数问题转化为两位数问题。
详细证明过程
假设：存在三个整数 a,b,c∈Za,b,c \in \mathbb{Z}a,b,c∈Z，满足 a+b=ca + b = ca+b=c 且 0≤a,b,c<1090 \leq a,b,c < 10^90≤a,b,c<109，其中 a,b,ca,b,ca,b,c 由三个特定字符集构建。
1. 个位加法的基础分析
由于 a+b=ca + b = ca+b=c，等式成立的必要条件是个位数字满足 a0+b0≡c0(mod10)a_0 + b_0 \equiv c_0 \pmod{10}a0 +b0 ≡c0 (mod10)（其中 x0x_0x0 表示整数 xxx 的个位数字）。
* 情况一：个位无进位
若 a0+b0=c0a_0 + b_0 = c_0a0 +b0 =c0 且 a0+b0<10a_0 + b_0 < 10a0 +b0 <10，此时取 a′=a0,b′=b0,c′=c0a' = a_0, b' = b_0, c' = c_0a′=a0 ,b′=b0 ,c′=c0 ，显然 a′,b′,c′<10<100a',b',c' < 10 < 100a′,b′,c′<10<100，命题得证。
* 情况二：个位有进位
若 a0+b0=c0+10a_0 + b_0 = c_0 + 10a0 +b0 =c0 +10（即向十位进位），此时需进一步分析十位数字的组合情况。
2. 基于进位条件的十位分析
假设个位进位为 111，若字符集 ScS_cSc 中不包含数字 111，则无法通过更高位的运算消除个位进位带来的影响，导致等式不成立。因此，若有解且个位进位，则 1∈Sc1 \in S_c1∈Sc 是必要条件。
* 此时，为使等式成立，十位数字需满足 a1+b1+1=c1a_1 + b_1 + 1 = c_1a1 +b1 +1=c1 （其中 x1x_1x1 表示整数 xxx 的十位数字），等价于 a1+b1=c1−1a_1 + b_1 = c_1 - 1a1 +b1 =c1 −1。若能找到满足此条件的 a1,b1,c1a_1,b_1,c_1a1 ,b1 ,c1 ，则可构造出两位数解 a′=10a1+a0,b′=10b1+b0,c′=10c1+c0a' = 10a_1 + a_0, b' = 10b_1 + b_0, c' = 10c_1 + c_0a′=10a1 +a0 ,b′=10b1
+b0 ,c′=10c1 +c0 ，且 a′,b′,c′<100a',b',c' < 100a′,b′,c′<100。
3. 多位数问题向两位数的转化
由于假设每一位加法均产生进位，对于任意长度的 a,b,ca,b,ca,b,c，其每一段连续两位的数字组合（首尾拼接）均需满足加法进位规则。因此，验证所有可能解的充分条件是验证所有两位数组合，即只需在 0≤a,b,c<1000 \leq a,b,c < 1000≤a,b,c<100 的范围内寻找解。
结论
通过对个位进位情况的分类讨论，结合多位数进位的普遍规律，证明了若存在满足 a+b=ca + b = ca+b=c 且 a,b,c<109a,b,c < 10^9a,b,c<109 的整数解，则必然存在一组解使得 a,b,c<100a,b,c < 100a,b,c<100。此结论将解空间显著缩小，为后续算法设计提供了理论依据。
参考代码
