# 快速乘

ps : 建議先去看[快速冪](/OBXWeBUOTH-Eo5FIcMIHDA),方法跟快速冪類似

如果要把兩個很大的數相乘且mod M,很有可能會溢位,那就要利用快速乘了

### 快速乘 : 把兩個數的乘法轉換成加法

題目:

(A×B)%M

把B轉乘二進制
假設B=14₁₀=(1110)₂= (2^3^)×1 + (2^2^)×1 + (2^1^)×1 + (2^0^)×0

帶入題目
A×((2^3^)×1 + (2^2^)×1 + (2^1^)×1 + (2^0^)×0)
= A×(2^3^)×1 + A×(2^2^)×1 + A×(2^1^)×1 + A×(2^0^)×0
= (2^3^×A)×1 + (2^2^×A)×1 + (2^1^×A)×1 + (2^0^×A)×0

### 從後面開始運算,由右往左,每次B>>=1 , a+=a

由A前面的係數可知,每次都多乘2,所以每次的運算都是A*=2

每個元素最後面的0或1決定此元素是否有效,也就是說,如果是0就不用裡他,是1再把前面的數加到答案裡,此0跟1可由B&1得到

int mul(int a,int b){
    int ans=0;
    while(b!=0){
        if(b & 1){
            ans+=a;
        }
        b/=2;
        a*=2;
    }
    return ans;
}

改成位元運算

int mul(int a,int b,int m){
    int ans=0;
    while(b){
        if(b & 1){
            ans+=a;
        }
        b>>=1;
        a<<=1;
    }
    return ans;
}

取模

int mul(int a,int b,int m){
    a%=m;b%=m;
    int ans=0;
    while(b){
        if(b & 1){
            ans=(ans+a)%m;
        }
        b>>=1;
        a=(a<<1)%m;
    }
    return ans;
}

例題 : <a href="https://zerojudge.tw/ShowProblem?problemid=b430">b430: 簡單乘法</a>

#include <bits/stdc++.h>
#define int long long
using namespace std;

int mul(int a,int b,int m){
    a%=m;b%=m;
    int ans=0;
    while(b){
        if(b & 1){
            ans=(ans+a)%m;
        }
        b>>=1;
        a=(a<<1)%m;
    }
    return ans;
}

signed main(){
    cin.sync_with_stdio(0),cin.tie(0);

    int a,n,b;
    while(cin >> a >> b >> n){
        cout << mul(a,b,n) << '\n';
    }
    return 0;
}