在c中乘以大數字

Question

我有兩個整數x和y 讓我們說x = 10^5和y = 10^8現在我必須乘以數字並將它們存儲在變量z中。我不需要確切的價值。 z可以以100000009爲模回答。我該怎麼做？

在此先感謝

Answer 1

#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 2

您可以使用對數和指數。指數是函數f（x）= e^x，其中e是等於2.71828182845的數學常數... 對數（用ln標記）是指數的倒數。由於In（a * b）= In（a）+ In（b），a * b = e ^（In（a）+ In（b））。

備註：
該方法是在計算機之前使用的。

Answer 3

一般來說，你應該依靠關係：

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

在這種特殊情況下，它沒有太大的幫助，因爲你的a和b都比n較小，但對於更大的a或b此擔保您需要處理的最大乘積大小爲n^2而不是a * b。

在64位系統上，當前值n^2將適合於long之內。如果你預計值較大，那麼你需要一個任意精度的數學庫，如GMP。