基本算法之龟速乘

题目

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;
}