基本算法之龟速乘

题目

90. 64位整数乘法

算法标签: 快速幂, 龟速乘

思路

利用二进制拆分思想, 因为直接计算乘法时间复杂度是$O(1)$, 但是二进制拆分时间复杂度是$O(\log n)$, 因此叫龟速乘

代码

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef long long LL;int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);LL a, b, mod;cin >> a >> b >> mod;LL ans = 0;while (b) {if (b & 1) ans = (ans + a) % mod;a = (a + a) % mod;b >>= 1;}cout << ans << "\n";return 0;
}