多进制数的乘法时间复杂度 O(n)?

举个🌰，比如 7-5-3 进制数，可以表示 0-104 ，105 个整数

7-5-3 进制数跟 10 进制数的转换

0-0-0 表示 0 1-1-1 表示 1 2-2-2 表示 2 3-3-0 表示 3 4-4-1 表示 4 5-0-2 表示 5

以此类推

6-4-2 表示 104

10 进制数转换为 7-5-3 进制数很容易，求余即可。反过来，7-5-3 进制数转换为十进制数可用中国剩余定理算 a-b-c to (a15 + b21 + c*70) mod 105.

显而易见，7-5-3 进制数的加法:

a-b-c + x-y-z = (a+x)-(b+y)-(c+z)，只需要对每位计算一次，完全不需要考虑进位。当然这个并不是大问题，计算机算加法也是可以同时并行计算每一位，并不是手算那种需要考虑进位的依赖。

有意思的是乘法:

a-b-c * x-y-z = (ax) mod 7-(by) mod 5-(c*z) mod 3

n 位的乘法只需要 O(n)，而非小学学的 O(n^2)，也比基于 FFT 的 O(nlog n log log n)快

其中最大的优点是可并行计算，只要计算单元够多，O(1)就能计算出乘法结果而没有进位的依赖.