我有一個數組<code>A</code>和<code>B</code>比較乘法

Question

，我們乘陣列A的所有元素，讓這個值稱爲MulA，與之相似我們爲B調用這個值MulB做。

現在，我們要比較這些值哪一個是更大的，我們能做的實際上不相乘的元素，因爲價值是爲了10^10和array length是高達10^6我們不能存儲我們的結果呢？

Answer 1

爲避免大型產品，您可以比較日誌總和：sum(log a for a in A)至sum(log b for b in B)。這是因爲(a1*a2*a3*...*an) = exp(log(a1)+log(a2)+...+log(an))和exp是一個增加功能。

這會引入一些數字錯誤（因爲log不是完全可計算的），但它在實踐中將工作得很好，除非產品彼此非常接近。

請注意，這既適用於產品很大時，也適用於產品很小時（例如，如果元素是可能性）。

Answer 2

使用64位整數（在C++中爲long long），它可以容納高達9 x 10^18（2^63-1）。不，沒有辦法比較兩個列表乘法而不乘以它們（模乘法運算規則在這裏不起作用）。

因爲值是階10^10和陣列長度爲高達10^6我們不能 商店我們的結果？

在最壞的情況下，乘以的值將是10 ^（10^7），它不適合任何數據類型。所以你需要在這裏使用Big Integer，它將所有內容都以字符串形式引入。

如果您需要一個簡單的C++大整數實現，我可以提供一個。謝謝。