【算法笔记】O(1)快速乘

对于大整数乘法来讲,一般使用快速乘
但不论是按10进制拆分或是二进制拆分,其复杂度均有log
今天鏼爷提供了一种O(1)的方法:
设所求为:a*b (%c)

1) a%c, b%c <= 1e9
这样的话,O(1)直接算就好

2) 其他情况
用long double计算\(k = \left\lfloor {\frac{{ab}}{c}} \right\rfloor\)
之后输出a*b-c*k即可
因为这样的话,不会出现一个分母特别大,分子特别小的情况,所以long double的精度能够满足要求了