64位整数乘法

快速乘

O(log) 快速幂思想

类似于快速幂的思想，把整数 b 用二进制表示，即

那么

因为 $_math_inline$a * 2^i=(a * 2^{i-1}) * 2$math_inline_$ ，若已求出 $_math_inline$a * 2^{i-1}\text{mod}p$math_inline_$ ，则计算 $_math_inline$a * 2^{i-1}\text{mod}p$math_inline_$ 时，运算过程中的每一步结果都不超过 $_math_inline$2 * 10^{18}$math_inline_$

O(1) 特殊情况下易精度丢失导致答案错误

利用 $_math_inline$a * b\text{mod}p = a * b-\lfloor a * b/p \rfloor * p$math_inline_$

首先，当 $_math_inline$a,b < p$math_inline_$ 时， $_math_inline$a * b/p$math_inline_$ 下取整以后也一定小于 $_math_inline$p$math_inline_$ 。我们可以用浮点数执行 $_math_inline$a * b/p$math_inline_$ 的运算，而不用关心小数点之后的部分。long double 在十进制下有效位为 18~19 位。当浮点数的精度不足以保存精确数值时，它会像科学计数法一样舍弃低位，正好符合我们的要求。

虽然 $_math_inline$a * b$math_inline_$ 和 $_math_inline$\lfloor a * b/p \rfloor * p$math_inline_$ 可能很大，但是两者的差一定在 0~p-1之间。所以我们用 long long 来保存 $_math_inline$a * b$math_inline_$ 和 $_math_inline$\lfloor a * b/p \rfloor * p$math_inline_$ 各自的记过。整数运算溢出相当于舍弃高位，也正好符合我们的要求。

Code

 1// O(1)
 2ll mul(ll a, ll b, ll p) {
 3	return ((__int128)a*b)%p;
 4}
 5// O(1)
 6ll mul(ll a, ll b, ll p) {
 7	a %= p; b %= p;
 8	ll c = (long double)a * b / p;
 9	ll ans = a * b - c * p;
10	return (ans % p + p) % p;
11}
12// O(log)
13ll mul(ll a, ll b, ll p) {
14	ll ans = 0;
15	while (b) {
16		if (b & 1) ans = (ans + a) % p;
17		a = a * 2 % p;
18		b >>= 1;
19	}
20	return ans;
21}

Problem

64 bit integer multiplication