快速乘

02快速乘

因为我们知道乘法有的时候会溢出，即使是 long long 也可能在乘法时因为结果过大溢出（当模数也是 long long ）。所以我们需要寻找一种能高效完成乘法操作并且不会爆 long long 的算法，也就是快速乘。本文也将对几种常用快速乘及其优化技巧做个总结。

1. 复杂度为 O(log) 的快速乘：

我们知道乘法其实就是把很多个加法运算合到一起。现在我们的乘法会爆范围，那我们就把它转化为加法。但是我们不可能一个一个的加，这样复杂度会是 O(n) 级别。所以我们模仿2进制加法操作来完成。

inline ll ksc(ll x,ll y,ll p){//计算x乘y的积
    ll res=0;//加法初始化
    while(y){
        if(y&1)res=(res+x)%p;//模仿二进制
        x=(x<<1)%p; y>>=1;//将x不断乘2达到二进制
    }return res;
}
// ll 表示 long long

当然我们不一定要仿照2进制，也可以是其他进制，只要中间算每一位上数字代表值时不会爆 longlong 就行！

2. 优秀的 STL 结构：__int128

__int128是c++自带的一个数据类型，顾名思义，它可以装下 $2^{128}$级别的大数据，而且可以直接进行各种加减乘除之类的操作（复杂度很接近 O(1) ），不过它需要手写输出（但其实我们只需要在运算时用一下就可以了，就像下面这样：）

long long ans=((__int128)x*y)%p

不过有一点遗憾的就是：联赛中基本上不会允许使用这个数据类型的

3. 非常优秀的 O(1) 快速乘

这个东西最初我感觉很不靠谱，但它就是能算出来正确答案。它就是用 long double 来进行优化取模运算。让我们先看一代码实现吧：

inline ll ksc(ll x,ll y,ll p){
    ll z=(ld)x/p*y;
    ll res=(ull)x*y-(ull)z*p;
    return (res+p)%p;
}
// ll 表示 long long
// ld 表示 long double
// ull 表示 unsigned long long
// 一种自动溢出的数据类型（存满了就会自动变为0）

看到这份代码有没有感到十分奇怪？ 它中间是直接用了乘法操作的啊！这不直接爆掉了吗？

但是它就是可以算出正确答案来。因为它其实很巧妙的运用了自动溢出这个操作，我们的代码中的 $z$ 就表示 $⌊x×y/p⌋$ ，所以我们要求的就变成了 $x×y−⌊x×y/p⌋×p$ ，虽然这两个部分都是会溢出的，但（unsigned）保证了它们溢出后的差值基本不变，所以即使它会溢出也不会影响最终结果的！

4. 关于快速乘的灵活转化：

我们知道快速乘的原理其实就是乘法转加法（上面这种不算），但是这是可以根据题目性质灵活转变的，我们如何转成加法决定了我们的复杂度，就像如果模数并没有超过int范围很多，那我们适当的运用乘法分配律可以让复杂度非常接近 O(1) ：

inline ll ksc(ll x, ll y, ll P){
    ll L=x*(y>>25)%P*(1<<25)%P;
    ll R=x*(y&((1<<25)-1))%P;
    return (L+R)%P;
}

在保证运算不会爆long long的前提下，我们可以尽量优化其复杂度，就像上述代码在模数小于 $10^{12}$的情况下完全变成了 O(1) 级别，在某些题目中会十分优秀！

5. 一些经常需要快速乘的算法：

Miller rabin 判大质数

Pollard Rho 大数因子寻找

BSGS 大步小步算法