一个数和这个数十进制位各位求和在模 9 意义下同余

方便起见,设该数 $N$ 仅有三位,可表示为 $xyz$:

\[\begin{aligned} \therefore &N = x \times 100 + y \times 10 + z \\ \therefore &N = x \times 99 + y \times 9 + x + y + z \\ \therefore &N \equiv x + y + z \pmod 9 \\ \end{aligned}\]

也就是说模 $9$ 下,$N$ 和 $x+y+z$ 具有相同余数(显然不管 $N$ 有几位也都是成立的)。

回到题目中

当 $N$ 是 $9$ 的倍数,

  • 对 $N$ 按位求和得到的 $N_1$ 也是 $9$ 的倍数,
  • 对 $N_1$ 按位求和得到的 $N_2$ 也是 $9$ 的倍数,
  • $\dots$
  • 每迭代一次,$N_i$ 的值都在变小,直到 $N_i$ 为 $9$ 不再变小, 所以最终结果 $addDigits(N)$ 是 $9$。
if(N % 9 == 0) return 9; 

当 $N$ 不是 $9$ 的倍数,迭代过程中每一步的 $N_i$ 和 $N$ 都同余, 所以最终结果就是 $N \mod 9$。

if(N % 9 != 0) return N % 9;

合并写法

前两行代码已经可以解题了,但其实可以不分类讨论,可直接合并结果。 利用带余除法(欧几里德除法),给定 $N$ 有

\[N = k \times 9 + R \begin{cases} 当 R = 0 ,最终答案为 9 \\ 当 R \neq 0 ,最终答案为 R \end{cases}\]

为了让两种情况有相同结果形式,我们把第一种情况变形:

\[N = k \times 9 + R \begin{cases} 当 R = 9 ,最终答案为 R \\ 当 R \neq 0 ,最终答案为 R \end{cases} \implies N = k \times 9 + R \begin{cases} 当 R = 9 \\ 当 R \neq 0 \end{cases} ,最终结果都是 R\]

之所以能把第一种情况写成 $R = 9$, 这还是考虑到当 $N$ 是 $9$ 的倍数,肯定存在整数 $k$ 使得 $N = k \times 9 + 9$。 当然在这种情况下这里的带余除法不再是往常所见带余除法了, 往常的带余除法余数 $r$ 会落在 $[0 , 9)$, 但是这里的”余数” $R$ 却落到了 $[1,9]$,修正了余数的范围。

这里我主要想起来数论中常见的余数其实是最小非负剩余,但我们可以人为定义余数落在哪个区间里面。 给定整数 $a$ 和 $b$,只要余数 $R$ 有合适的活动空间(长度为 $b$ 的一段连续区间), 式子 $a = kb + R$ 都是可以成立的。可以这样理解:数轴上有一个长度为 $b$ 的区间, 不管这个区间起点在哪,都可以让 $a$ 按长度为 $b$ 的步伐跨步若干次到该区间中, 即整数 $k$ 的存在是必定的,于是 $R$ 随之可以确定, 且 $R$ 的活动范围随区间起始位置的调整会响应地调整。

对于这道题目,余数 $R$ 的范围在 $[1,9]$,为方便叙述我们把这个余数就叫做最小正剩余吧。 于是问题转化为:给定整数 $N$,构造等式 $N = k \times 9 + R$ 满足 $R \in [1 , 9]$,解出的 $R$ 就是要输出的结果。 这里的 $R$ 仍不好求出,不能直接调用程序语言里面的取余,因为程序中取余得到的余数(记为 $r$)是最小非负剩余。 但好在二者之间还是有关系的,最小正剩余可以利用最小非负剩余求解结果:

\[N = k \times 9 + R,R \in [1,9]\]

左右两边减一:

\[N - 1 = k \times 9 + R - 1,R - 1 \in [0,8]\]

记 $r = R - 1$:

\[N - 1 = k \times 9 + r,r \in [0,9)\]

于是 $r$ 恢复成最少非负剩余,$r$ 可以在计算机中直接求出,求出 $r$ 后加一就是最终期望得到的 $R$了。

int addDigits(int num) 
{
    int r = (num - 1) % 9;
    int R = r + 1;
    return R;
}
return (num - 1) % 9 + 1;

文章为 C#.NAME 原创,禁止转载。