逐位相加法-快速取模算法

2019-04-14 11:59发布

任意两个整数 A B 做乘法
C = A×B
然后把 A,B, C的十进制每个数分别相加,如果和大于10就继续把每个数相加,直到只剩一位数,分别得到 A1 B1 C1
D = A1 × B1,对D也进行每个数相加直到只剩下一位得到 D1
则 C1 = D1 举例: 835 × 267 = 222945 835 => 8 + 3 + 5 = 16 => 1 + 6 = 7
267 => 2 + 6 +7 = 15 => 1 + 5 = 6
6 * 7 = 42 => 4 + 2 = 6 222945 => 2 + 2 + 2 + 9 + 4 + 5 = 24 => 2 + 4 = 6 原理是:
(A%9 * B%9) % 9 == (A * B) % 9
% 是C 语言取模算符
逐位相加是快速计算对 9 取模的方法