跳转至

快速乘

前置知识

龟速乘，long double

目的

快速乘原理

2009年全国信息学奥林匹克冬令营论文，成都七中，骆可强

image-20240702161411526

关键的话：

我们可以预见其差是一个 64bit 可容纳的正整数，

那么溢出部分的差仅可能为 0 或者 1。

如果溢出部分差为 1，就是负数的情况。

思路，利用 \(a * b \ mod \ p=a*b-\lfloor a * b \ / \ p \rfloor *p\) 。

首先，当 \(a, b < p\) 时，\(a*b \ / \ p\) 向下取整一定小于 \(p\)。

有些传统实现会用 long double 估计商，再校正余数。但 long double 的精度由平台决定，而且仅用浮点估计并不能自动保证所有 \(10^{18}\) 范围输入都正确。若采用这种方法，必须配合严格的误差边界证明和余数校正。

C++ 中有符号整数溢出是未定义行为，不能把它当作“舍弃高位”来依赖。在 GCC/Clang 竞赛环境中，可以使用 __int128 安全保存两个 64 位整数的乘积。

模意义下大整数乘法

64位整数乘法，题目链接：https://www.acwing.com/problem/content/92/

求 \(a\) 乘 \(b\) 对 \(p\) 取模的值，其中 \(1 \leq a, b, p \leq 10^{18}\)。

使用 128 位中间结果完成乘法和取模，避免 64 位有符号溢出。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll mul(ll a, ll b, ll p) {
    return static_cast<ll>((__int128)a * b % p);
}

int main() {
    ll a, b, p;
    cin >> a >> b >> p;

    cout << mul(a, b, p) << '\n';

    return 0;
}

__int128 不是 ISO C++ 标准类型，但 GCC/Clang 及常见竞赛环境支持它。若平台不支持，可使用类似快速幂的“倍增加法”实现模乘。

关于 long double

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    double a = 3.14159265358979323846264338327950288419716939937510;
    long double b = 3.14159265358979323846264338327950288419716939937510L;

    cout.precision(50);

    cout << a << '\n';
    cout << b << '\n';
    cout << "3.14159265358979323846264338327950288419716939937510" << '\n';

    return 0;
}

image-20240702164615033

总结

快速乘需要避免有符号整数溢出；竞赛环境中可使用 __int128，或使用倍增加法。

参考