浅谈快速乘

前言

想必大家都听说过快速幂

那快速乘是个什么东西呢？

考虑取模操作a*b%p，1^10 ≤ a,b,p ≤ 2^10

可以发现在 long long情况下，我们直接取模会溢出

那么怎么办呢？

题目链接：https://www.luogu.com.cn/problem/U203580

快速乘

注：本文根据q779本人的习惯，所有的int都宏定义为了long long

标准快速乘

时间复杂度 \(O(\log b)\)，且正确性完备

类似于快速幂，具体见代码

#define int long long

int ksc(int a,int b,int p)
{
    int ans=0;
    while(b)
    {
        if(b&1)ans=(ans+a)%p;
        a=(a<<1)%p;b>>=1;
    }
    return ans;
}

__int128_t

这是个自带的数据类型，而且根据我查阅到的资料来看，有一点点不太靠谱的感觉

它能存到 \(2^{128}\) 的数量级，且NOIP等赛事中是明确可以使用的

而且本机编译通过了（g++ (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0）

#define int long long

cout << (int)((__int128_t)a*b%p) << endl;
cout << (int)((__int128)a*b%p) << endl; // 这样写也是可以的

据说win上不能用，因此建议还是使用标准快速乘吧

O(1)快速乘

一个正确性不太靠谱但是在这个数据范围下能算出正确答案的神奇算法

好像出自 2009年全国信息学奥林匹克冬令营论文《论程序底层优化的一些方法与技巧》骆可强

它利用了long double的范围来算的

#define int long long

int ksc(int a,int b,int p)
{
    int t=(long double)a/p*b;
    int ans=a*b-t*p;
    if(ans<0)ans+=p;
    if(ans>=p)ans-=p;
    return ans;
}