JZTXT

快速幂 & 龟速乘 & 快速乘

发布时间 2023-11-12 17:47:01作者: blind5883

龟速乘和快速乘都是为了防止模数大于int, 导致爆long long的情况

关于O(1)快速乘和关于其特判的原因 - :Dra - 洛谷博客 (luogu.com.cn)

快速幂(待补)

龟速乘

龟速乘和快速幂一样, 都是利用了二进制的原理,
把 a * k 的 k拆成二进制数, 根据每一位凑出来

如k = 5 = 101（2）
就可以用a + 4a凑出来

#代码如下
LL qmul(LL a, LL k, LL p) // 龟速乘
{
    LL res = 0;
    while (k)
    {
        if (k & 1) res = (res + a) % p;
        a = (a + a) % p; 
        k >>= 1;
    }
    return res;
}

快速乘

这玩意我也是新学, 但确实很巧妙
原理就是a % b == a - a/b * b
关于O(1)快速乘和关于其特判的原因 - :Dra - 洛谷博客 (luogu.com.cn)
这篇博客讲的好
rt = a * b - (LL)((double)a / p * b + 0.5) * p;
先看这句话, 后面(LL)((double)a / p * b + 0.5)因为(double)的原因
所以不会爆掉, 前面a * b和 后面再乘一个p就会爆掉longlnog
但是没关系, 我们只需要它的差值, p是模数, p一定在longlong范围内
(这也是, 这个技巧正确的原因)
那么a * b - (LL)((double)a / p * b + 0.5) * p;的结果一定也在longlong内
因为a % b == a - a/b * b 这个原理
这就把结果求出来了, 但是因为double 会有精度问题
在(double)a / p * b中会损失精度, 它实际上就是接近未知的x的一个数 , 但始终达不到
注意double变longlong会把小数点拦腰截断, 也就是下取整

如果精度损失使它(double)a / p * b超过x且它下取整后的结果比x大1,
那么就会让rt成为负数
如果精度损失使他小于x, 同理就会让rt变成大于mid的正数

所以我们会得到一个和正确答案差值绝对值为mod或0的答案

考虑当 (long double)a / mod * b 的真实值是一个十分接近但小于某个整数 x 的值, 在计算过程中的精度损失会使其超过 x 并且使向下取整后的结果大 1, 同理其十分接近但大于某个整数会使结果小 1 , 故我们得到的答案与正确值之差的绝对值是 mod 或 0.

这里引用博客中的话

这里就可以看看那个+0.5的作用了
这相当于四舍五入, 这会使得计算出来的rt不会比正确答案大, 而少判断一种情况, 减少常数

如果不加的话就需要判断让rt大于mid的情况

#代码
LL fqmul(LL a, LL b, LL p) // 快速乘
{
    LL rt = a * b - (LL)((double)a / p * b + 0.5) * p;
    if (rt < 0) rt += p; // 判断小于0的情况
    return rt;
}
// 或者
LL fqmul(LL a, LL b, LL p)
{
	LL rt = a * b - (LL)((double)a / p * b) * p;
	if (rt < 0) rt += p;
	if (rt >= mid) rt -= mid;
	return rt;
}

模版

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

LL n = 142, m = 12343, mod = 1e10 + 7;

LL fqmul(LL a, LL b, LL p) // 快速乘
{
    LL rt = a * b - (LL)((double)a / p * b + 0.5) * p;
    if (rt < 0) rt += p;
    return rt;
}

LL qmul(LL a, LL k, LL p) // 龟速乘
{
    LL res = 0;
    while (k)
    {
        if (k & 1) res = (res + a) % p;
        a = (a + a) % p; 
        k >>= 1;
    }
    return res;
}

LL qmi(LL a, int k, LL p) // 快速幂
{
    LL res = 1;
    while (k)
    {
        if (k & 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

LL l_qmi(LL a, int k, LL p) // 龟速_快速幂
{
    LL res = 1;
    while (k)
    {
        if (k & 1) res = qmul(res, a, p);
        k >>= 1;
        a = qmul(a, a, p);
    }
    return res;
}

LL f_qmi(LL a, int k, LL p) // 快速_快速幂
{
    LL res = 1;
    while (k)
    {
        if (k & 1) res = fqmul(res, a, p);
        k >>= 1;
        a = fqmul(a, a, p);
    }
    return res;
}


int main()
{
    cout << qmi(n, m, mod) << endl; // 会溢出 爆long long
    cout << l_qmi(n, m, mod) << endl; // O(logn * logn) 
    cout << f_qmi(n, m, mod) << endl; // O(logn)
    
    return 0;
}