快速乘的不同实现方式

有时我们需要解决这样的问题：求 $a\times b\mathrm{mod}P$。一般来说，如果 $P$ 是一个 int 范围内的模数，那么直接使用 1ll * a * b % P 转化为 long long 进行运算即可。但是，如果 P 为 long long 范围内的模数，又该如何操作？

方法1

类似于 int 范围内找 long long，我们同样可以找 long long 的上位类型： __int128。即使用 (__int128)a * b % P 来计算，时间复杂度 $O(1)$。但是问题是，__int128 并非在 GCC 标准内。

方法2

俗称的龟速乘。一般来说，P 尽管在 long long 范围内，但还是要保证加法运算不溢出（如果会溢出，倒是可以用 unsigned long long 避免），所以我们可以用类似快速幂的方法写出“快速乘”：

ll mul(ll a, ll b, ll P) {if(a < b) swap(a, b);ll ret = 0;for(; b; b >>= 1, (a += a) %= P) if(b & 1) (ret += a) %= P;return ret;
}

时间复杂度 $O(\log V)$，比较慢。

方法3

使用 long double 的黑科技。

ll mul(ll a, ll b, ll P) {ll c = (long double)a / P * b;ll res = (unsigned long long)a * b - (unsigned long long)c * P;return res;
}

如何理解？首先 ⌊ a b P ⌋ \left\lfloor \dfrac{ab}{P}\right\rfloor ⌊Pab​⌋ 在 $P$ 的范围内，采用 16 字节的 long double 过渡可以无误差准确计算这个值。根据模的定义：

a b m o d P = a b − ⌊ a b P ⌋ ⋅ P ab\bmod P = ab-\left\lfloor\dfrac{ab}{P}\right\rfloor\cdot P abmodP=ab−⌊Pab​⌋⋅P

这两个值都可能溢出，但是由于 unsigned long long 的溢出是良定义的，所以溢出了，差值还是可以用。

时间复杂度 $O(1)$，但是比较通用。（注意有些平台上 long double 不一定是 16 字节，但大部分是）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！