O1快速乘

O(1)求解：\(a*b \% p\)
范围：a , b , p\(\le 10^{18}\)

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

推倒方式：
\(a * b \% p = a * b - \left\lfloor\dfrac{a*b}{p}\right\rfloor*p\)
后半部分可以用小数解决。
前面我们可以利用long long溢出的性质。
\(a * b \% X +\left\lfloor\dfrac{a*b}{p}\right\rfloor*p \% X = (a * b - \left\lfloor\dfrac{a*b}{p}\right\rfloor*p )\% X\)
由于答案不会超过long long所以可行。
显然，小数那里有误差

LL mul(LL a , LL b, LL p) {
    LL c = (long double) a * b / p;
    long long ans = a * b - c * p;
    if(ans < 0) ans += p;
    else if(ans >= p) ans -= p;
    return ans;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄