title: 快速乘
date: 2022-10-06 10:22:50
tags: 算法

概念

• 与快速幂差不多{% post_link 算法/快速幂 %}
• 都是通过转换二进制乘法

举例：
2x3 = 6 =>
\(2^{\left(11\right)_2}=2^{2^1\times1}+2^{2^0\times1}\)

时间复杂度

\(O(logN)\)

以前为\(O(N)\)

代码

typedef long long ll;
int fast_multiplication(int a,int b,int mod){
    int ans = 0;
    while(b){
        if(b&1){
            ans = (ll) (ans+a)%mod;
        }
        b>>=1;
        a = (ll)a*2%mod;

    }
    return ans;
}