求解将整数N拆为仅含1/2/3数位的数之和的最小K相关问题

首先我们先明确问题核心：给定整数N，求最小的K，使得N可以表示为K个仅由数字1、2、3组成的正整数的和。

核心思路转换 #

我们不需要纠结官方题解中的「好数」后续推导，可以换一个更直观的角度拆解问题：

• 所有仅由1、2、3组成的数，都可以拆成若干个全1数的和：比如3 = 1+1+1，12 = 11 +1，23 = 11+11+1，每一位的数字就代表对应长度的全1数的个数。
• 反过来，如果我们能用t个全1数（1、11、111、1111……）相加得到N，那么最多只需要ceil(t/3)个目标数：因为每3个相同长度的全1数可以合并为一个数字3，2个可以合并为数字2，1个保留为数字1，刚好符合每一位只能是1、2、3的要求。

所以问题就转化为：找到最小的t，使得N可以表示为t个全1数的和，最终答案就是ceil(t/3)。

公式推导 #

全1数的通项公式为R_m = (10^m - 1)/9，我们设用了a_1个R_1、a_2个R_2……a_k个R_k，那么：
$$
N = a_1 \times \frac{10^1 -1}{9} + a_2 \times \frac{10^2 -1}{9} + ... + a_k \times \frac{10^k -1}{9}
$$
两边乘以9可得：
$$
9N = a_1(10^1 -1) + a_2(10^2 -1) + ... + a_k(10^k -1)
$$
整理后得到：
$$
a_1 \times 10 + a_2 \times 10^2 + ... + a_k \times 10^k = 9N + (a_1 + a_2 + ... +a_k)
$$

我们令t = a_1 + a_2 + ... +a_k（也就是全1数的总个数），等号左边的数有两个性质：

1. 个位一定是0（所有项都是10的倍数），所以9N + t的个位必须是0，即t ≡ (-9N) mod 10
2. 等号左边的数的数位和一定≤t：因为如果a_i≥10就会产生进位，每进位一次数位和减少9，所以数位和 = t - 9×总进位次数 ≤ t

极简解题步骤 #

根据上面的推导，我们只需要几步就能得到答案：

1. 计算S = 9 * N
2. 确定t的个位取值r：r = (10 - (S % 10)) % 10，初始t取最小的符合个位要求的正整数：如果r=0则初始t=10，否则t=r
3. 每次给t加10（保持个位不变），计算X = S + t的数位和sum_d，直到sum_d ≤ t，此时的t就是最小的全1数总个数
4. 最终答案K = (t + 2) // 3（整数除法等价于向上取整t/3）

示例验证 #

比如N=10：

1. S=9*10=90，r=(10-0)%10=0，初始t=10
2. X=90+10=100，数位和是1 ≤10，满足条件
3. K=(10+2)//3=4，和实际结果一致

再比如N=12：

1. S=9*12=108，r=(10-8)%10=2，初始t=2
2. X=108+2=110，数位和是1+1=2 ≤2，满足条件
3. K=(2+2)//3=1，正确

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