参考文献

OI Wiki

这里主要说快速乘的模板

龟速乘是$O(logn)$的算法
快速乘是可以处理long long以及$O(1)$的算法

解决的问题

公式

$$a*b \% m = a * b - \lfloor \frac{ab}m \rfloor * m$$

代码

typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
LL binmul(LL a, LL b, LL m) {
    ULL c = (ULL)a * b - (ULL)((LD)a / m * b + 0.5L) * m;
  return (c + m) % m;
}