用来求解 r=a*b%p 中的 a*b 超过 long long 范围导致爆 long long 的算法，其中 a，b，p，r 均为 long long 类型
传统上我们可以仿照 快速幂 来进行快速乘
复杂度 $\mathcal{O}{(\log_2^n)}$
1typedef long long ll;
2ll qm(ll a, ll b, ll p) //qm = quick multiply; a * b % p
3{
4 if(!b) return 0;
5 if(b&1) return (a+qm(2*a%p, b>>1, p)) % p;
6 else return qm(2*a%p, b>>1, p) % p;
7}
另一种方法 是利用计算机的性质，和一些求模性质
求 a*b%p 时，我们引进一个模数 $m$ 满足 $(m>p)$，有以下公式成立
$$ \begin{align*}a\cdot b \bmod p &= a\cdot b - p\cdot\lfloor\frac{a\cdot b}{p}\rfloor = (a\cdot b - p\cdot\lfloor\frac{a\cdot b}{p}\rfloor)\bmod m \newline &= (a\cdot b \bmod m -p \cdot \lfloor\frac{a}{p}\cdot b\rfloor\bmod m)\bmod m \end{align*} $$
显然这个 $m$ 可以是 long long 表示的范围大小 $2^{64}$，而计算机中两个 long long 类型的数据做算术运算是隐式求余 $2^{64}$ 的，其求余结果在 $[-2^{63}, 2^{63}-1]$ 之间，由于 $p$ 用 long long 表示，则 $p<m/2$，上述计算式结果必为正，在计算机中所有 $\bmod m$ 都可以直接去掉，而不会影响结果的正确性。
1typedef long long ll;
2ll qm(ll a, ll b, ll p)
3{
4 return a*b - p*(ll)((long double)a/p*b);
5}
假如不考虑浮点数精度问题，以上代码则可直接求出 a*b%p 的准确值，但是 long double 并不能很好的表示整数部分。其整数部分会产生 -1, +1, 0 三类的偏差。比如 $5$ 被表示成 $4.99999\cdots$ 其整数部分少了$1$，$1.9999999999\cdots$ 表示成 $2.000000000$，其整数部分多了 $1$，反映到结果上有：
$p\cdot\lfloor\frac{a}{p}\cdot b\rfloor\bmod m \to p\cdot(\lfloor\frac{a}{p}\cdot b\rfloor + x)\bmod m,\ x\in(-1,0,1) $
显然无论 $x$ 取何值，结果 $\bmod \ p$ 都是不变的，假设正确答案是 $rest$ 那么上述代码得到的结果为
$(rest+p\cdot x)\bmod 2^{64},\ x\in(-1,1,0),\ rest\in[0,p-1]$
模 $2^{64}$ 在计算机中不是表示成 $[0, 2^{64}-1]$ 而是表示成 $[-2^{63}, 2^{63}-1]$
所以当 $x$ 为 $-1$ 时 上述代码变成了个负数，结果出错，需 +p 后为正确答案
$x$ 为 $1$ 时，$rest + p\cdot x$ 当 $p\leqslant \frac m4$ 时在计算机中表示为正数，当 $\frac m4 < p < \frac m2$ 时在计算机中表示为负数，比如 rest = 6e18, p = 7e18+1 此时 $rest+p$ 在计算机中 rest + p = -5446744073709551616
总结，无论 $x$ 为 $-1,0,1$ ，若结果为负则 +p 即可，若结果为正则 %p 即可
复杂度 $\mathcal{O}(1)$
1typedef long long ll;
2ll qm(ll a, ll b, ll p)
3{
4 a%=p, b%=p;
5 ll r = a*b - (ll)((long double)a/p*b)*p;
6 return r < 0 ? r+p : r%p;
7}
讨论
代码中 a%=p, b%=p 的必要性，当 long double 能够表示 $\lfloor\frac{a}{p}\cdot b\rfloor$，则不必要。易知，其实对于超过 int 大小的 p 都不必加上求余。