龟速乘¶
前置知识¶
二进制
每一个正整数可以唯一表示为若干个指数不重复的 \(2\) 的次幂的和
快速幂思想
目标¶
龟速乘模板，加深对二进制的理解
模意义下大整数乘法¶
64位整数乘法，题目链接：https://www.acwing.com/problem/content/92/
求 \(a\) 乘 \(b\) 对 \(p\) 取模的值，其中 \(1 \leq a, b, p \leq 10^{18}\)。
a 和 b 都很大，直接乘，会爆 long long（龟速乘的应用场景）
利用类似快速幂的思想，把整数 b 用二进制表示，即 \(b=c_{k-1}2^{k-1} + c_{k-2}2^{k-2} + ... + c_02^0\)，
那么，\(a*b=c_{k-1}*a*2^{k-1} + c_{k-2}*a*2^{k-2} + ... + 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 \ p\) 时，运算过程中，每一步的结果都不超过 \(2*10^{18}\)，仍然在 64 位整数 long long 的表示范围内。
所以，通过递推求出每个乘积项。当 \(c_i=1\)时，把该乘积项累加到答案中即可。
时间复杂度为 \(O(log_2b)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mul(ll a, ll b, ll p) {
ll ans = 0;
for (; b; b >>= 1) {
if (b & 1) ans = (ans + a) % p;
a = a * 2 % p;
}
return ans;
}
int main() {
ll a, b, p;
cin >> a >> b >> p;
cout << mul(a, b, p) << '\n';
return 0;
}
总结¶
通过龟速乘，可以更好的理解二进制
每一个正整数可以唯一表示为若干个指数不重复的 \(2\) 的次幂的和
常与快速幂搭配使用，应对数据相乘会爆 long long 的情况