位运算
2026-04-13
龟速乘
给定 a,b,p≤1018,求 a×bmodp 的值。
一般的解决办法是写个高精度,但是太麻烦了,有没有简单一点的呢?
有的有的,根据快速幂的思想,a×b 其实就是 b个aa+a+⋯+a,因此我们可以将其二进制分解,每次加若干个 a 即可。
时间复杂度 O(logV),其中 V 是值域。(跟高精度差不多)
2026-04-13
给定 a,b,p≤1018,求 a×bmodp 的值。
一般的解决办法是写个高精度,但是太麻烦了,有没有简单一点的呢?
有的有的,根据快速幂的思想,a×b 其实就是 b个aa+a+⋯+a,因此我们可以将其二进制分解,每次加若干个 a 即可。
时间复杂度 O(logV),其中 V 是值域。(跟高精度差不多)