c++ - Cで大きな数を掛ける

Question

2 つの整数 x と y があります。x= 10^5 と y = 10^8 としましょう。次に、数値を乗算して変数 z に格納する必要があります。正確な値を持っている必要はありません。z は 100000009 を法とする答えを持つことができます。どうすればよいですか?

前もって感謝します

Answer 1

一般に、次の関係に依存する必要があります。

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

aこの特定のケースでは、とbはどちらも よりも小さいためあまり役に立ちませんnが、より大きなaorbの場合、処理する必要がある最大の乗算はn^2と ではなくのオーダーであることが保証されます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)) です。

注意:
この方法は、コンピュータが登場する前に広く使用されていました。