AcWing 90. 64位整数乘法
因为 C++ 内置的最高整数类型是 64 位，若运算 $a * b \mod p$ 中的三个变量 $a, b, p$ 都在 $10^{18}$ 级别，则不存在一个可供强制转换的 128 位整数类型，我们需要一些特殊的处理办法。
方法一
类似于快速幂的思想，把整数 $b$ 用二进制表示，即
\[b = c_{k - 1} 2^{k - 1} + c_{k - 2} 2^{k - 2} + \cdots + c_0 2^0\]那么
\[a * b = c_{k - 1} * a * 2^{k - 1} + c_{k - 2} * a * 2^{k - 2} + \cdots + c_0 * a * 2^0\]因为
\[a * 2^i = (a * 2^{i - 1}) * 2\]若已求出 ${a * 2^i - 1 \mod p}$ ，则计算 $(a * 2^{i - 1}) * 2 \mod a$ 时，运算过程中每一步的结果都不超过 $2 * 10^{18}$，仍在64位整数 long long 的表示范围内，所以很容易通过 $k$ 次地推求出每个乘积项。
当 $c_i = 1$ 时，把该乘积项累计加到答案中即可。
时间复杂度为 $\mathcal{O}(\log_2 b)$。
完整代码：64位整数乘法1.cpp
方法二
利用 $a * b \mod p = a * b - \lfloor a * b / p \rfloor * p$，记 $c = \lfloor a * b / p\rfloor$。
若用浮点数直接计算 $a * b / p$，当浮点数的精度不足以保存精确数值时，它会舍去地位，所以得到的结果是 $c.___$，其中小数点之后的部分是不准确的。
long double 在十进制下的有效数字有 $18 \sim 19$ 位。
当 $a, b < p$ 时，$c$ 一定也小于 $p$，即 $c$ 在 $18$ 位以内。
故 long double 足够胜任保存整数部分的精确值 $c$。
再把结果强制转化为 unsigned long long 类型，即可得到整数 $c$。
当 $a * b$ 恰好能被 $p$ 整除时，由于精度误差，算出的 $c$ 可能比实际小 $1$，但这在取模一一下并不影响结果的正确性。
这一段只要知道有这么回事就可以了，不要去管它具体为什么是这样，这样就是这样，反正这个阶段学也学不懂浪费时间（bushi（逃
再算出 $a * b - c * p$。
因为 $a * b - c * p$ 实际上是 $a * b \mod p$，
所以 $a * b - c * p \leq p < 2^{64}$，
进而 $a * b - c * p = (a * b - c * p) \mod 2^{64}$。
因为 unsigned long long 自然溢出等价于对 $2^{64}$ 取模，所以我们用 unsigned long long 计算 $x = a * b$ 和 $y = c * p$，
再用 long long 计算 $(x\mod p-y\mod p)\mod p$，即可得到最终的结果。
时间复杂度为 $\mathcal{O}(1)$。
完整代码：64位整数乘法2.cpp