浅谈快速乘

想必大家都听说过快速幂

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

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

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

那么怎么办呢？

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

前言快速乘

标准快速乘__int128_tO(1)快速乘Montgomery算法 总结参考文献

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

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

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

#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;
}

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

它能存到 2 128 2^{128} 2128 的数量级，且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上不能用，因此建议还是使用标准快速乘吧

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

好像出自 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;
}

由于 a b − p ⌊ a b p ⌋ ab-pleftlfloordfrac{ab}{p}rightrfloor ab−p⌊pab​⌋的值是“固定”的

即这两部分都会溢出，但long long保证了它们的差值基本不变

因此溢出也不会影响计算

但是因为使用了除法操作，会存在精度问题，不建议在模数大于1e+12时使用（即 1 0 12 10^{12} 1012）

目前还没有学会，先留个坑以后补

介绍了一些快速算乘法取模的算法

本文目前还没有彻底完工，有待更新

[1] 快速乘总结

转载请说明出处