changed 2 years ago  
Published Linked with GitHub

快速乘

ps : 建議先去看快速冪,方法跟快速冪類似

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

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

題目:

(A×B)%M

把B轉乘二進制
假設B=1410=(1110)2= (23)×1 + (22)×1 + (21)×1 + (20)×0

帶入題目
A×((23)×1 + (22)×1 + (21)×1 + (20)×0)
= A×(23)×1 + A×(22)×1 + A×(21)×1 + A×(20)×0
= (23×A)×1 + (22×A)×1 + (21×A)×1 + (20×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;
}

例題 : b430: 簡單乘法



























#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;
}
Select a repo