思路

该方法与乘法相比较慢,这也是他为什么叫龟速乘的原因,但是它通常用在取模运算,比如两个long long的数字相乘并让你取模,这个时候普通的乘法就会爆掉,当然如果你想写高精度或者你用的python那就当我没说。所以就需要用到龟速乘,再乘的时候同时取模。

比如说3 * 7 = 3+3+3...+3,这样算下来就是7个3相加,此时将七转换为二进制就是0111,与快速幂思路相同。具体算式见下图,并与快速幂取模一样在过程去进行mod运算。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mul(ll a,ll b,ll c){
    ll ans = 0;//保存结果
    ll base = a;//每一次进行加的数字
    while(b){
        if(b&1){
            ans = (ans+base)%c;
        }
        base = (base*2)%c;
        b>>=1;
    }
    return ans;
}
int main(){
    ll a,b,c;
    cin>>a>>b>>c;
    cout<<mul(a,b,c);
    return 0;
} 

一只小菜鸡