力扣数论
数论（更新中）
1、数根
基础知识
数根又称数字根$（Digital root）$，是自然数的一种性质，每个自然数$num$都有一个数根。对于给定的自然数，反复将各个位上的数字相加，直到结果为一位数，则该一位数即为原自然数的数根。
计算数根的最直观的方法是模拟计算各位相加的过程，直到剩下的数字是一位数。
设自然数$num$的数根为$x$，设$a_i$为$num$每一位的数，则
$$
\begin{align}
num &=\sum_{i=1}^{n} a_i \times 10^i \
&=\sum_{i=1}^{n} a_i \times (10^i-1+1) \
&=\sum_{i=1}^{n} a_i \times (10^i-1)+\sum_{i=1}^{n} a_i
\end{align}
$$
当$i=0$时，$10^i-1=1-0=0$，是$9$的倍数；当$i\neq0$时，$10^i-1$是由很多个$9$组成，如$9、99、999$等，也是$9$的倍数，因此可以得到
$$
num % 9=\sum_{i=1}^{n} a_i%9
$$
例如258.各位相加就是用了这个性质，可以快速计算出数根！这个结论是很重要的！！！
设自然数$num$各个位的数相加为$num_1$，则$num%9=num_1%9$；设$num_1$各个位的数相加为$num_2$，则$num_1%9=num_2%9$。直到数$num_{n-1}$各个位相加的和为个位数，即数根设为$num_n$。若$num_n$不是$9$的倍数，则$num_n%9=num_n$，由于$num%9=num_n%9$，那么数根$num_n=num%9$；若$num_n$是9的倍数，则$num_{n-1}=9的倍数+num_n$，因此$num_{n-1}$是$9$的倍数，以此类推，num是9的倍数。
当然还一个漏洞，就是$num=0$，数根为0。
因此，数根$num_n$可以这么快速计算：
$$
num_n =
\begin{cases}
0 & \text{if } num =0 \
num%9 & \text{if }num%9\neq0\
9& \text{if }num%9=0 \text{ and } num\neq0
\end{cases}
$$