c++ - 在c中乘以大数

Question

我有两个整数 x 和 y 假设 x= 10^5 和 y = 10^8 现在我必须将这些数字相乘并将它们存储在变量 z 中。我不需要确切的值。z 可以得到模 100000009 的答案。我该怎么做？

提前致谢

Answer 1

一般来说，您应该依赖以下关系：

(a * b) % n = (a % n) * (b % n) % n

在这种特殊情况下，它没有多大帮助，因为您的aandb都小于n，但对于更大的aorb这保证了您需要处理的最大乘法是n^2and not a * b。

在 64 位系统上，您的当前值n^2将适合long. 如果您预期更大的值，那么您将需要一个任意精度的数学库，如GMP。

Answer 2

#include <iostream>
#include <cmath>

int main() {
    typedef unsigned long long ull;
    ull x = std::pow(10,5);
    ull y = std::pow(10,8);
    ull z = (x*y) % 100000009;
    std::cout << z << std::endl;
}

Answer 3

您可以使用对数和指数。指数是函数 f(x)=e^x，其中 e 是一个数学常数，等于 2.71828182845... 对数（由 ln 标记）是指数的倒数。

由于 ln(a*b)=ln(a)+ln(b)，所以 a*b=e^(ln(a)+ln(b))。

备注：
该方法在计算机之前被广泛使用。