64位整数乘法

佚名 4年前 (2020-06-22) 算法 1135人围观抢沙发百度已收录

64位整数乘法

求a乘b对p取模的值。

众所周知，64位整数乘以64位整数最大是可以达到128位的，所以使用long long就肯定会爆炸，所以我们可以使用128位整数。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include <bits/stdc++.h>

using namespace std;

int main() {
    long long _a, _b, _p;
    cin >> _a >> _b >> _p;
    __int128 a = _a, b = _b, p = _p;
    _p = a * b % p;
    cout << _p << endl;
}

那么我们如何能够不使用这样比较作弊的方案呢？
有一个类似于快速幂的思想，既然直接乘会爆炸，那我们把b拆成n个2^k的和，一点一点乘，反正最后取模和边做边取模是一样的。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){
    ll a, b, p;
    cin >> a >> b >> p;
    ll res = 0;
    while(b){
        if(b & 1)res += a, res %= p;
        a *= 2, a %= p;
        b >>= 1;
    }
    cout << res << endl;
}

当然我们还可以有更骚的操作

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main(){
    ll a, b, p;
    cin >> a >> b >> p;
    cout << (a * b - (ll)((long double) a / p * b ) * p + p ) % p << endl;
}