在C++中查找大數乘法的其餘部分

Question

我想問一些關於以下問題的幫助。我需要創建一個將兩個整數相乘的函數，並提取該乘法的剩餘部分除以某個數（簡而言之，（x * y）％A）。

我正在使用unsigned long long int來解決這個問題，但是A = 15！在這種情況下，x和y都是先前以模A計算的。因此，x * y可以大於2^64 - 1，因此溢出。

我不想使用外部庫。任何人都可以幫我設計一個簡短的算法來解決這個問題嗎？

在此先感謝。

Answer 1

如果你已經有x和y的mod A，爲什麼不使用它們呢？像，

如果

x = int_x*A + mod_x 
y = int_y*A + mod_y 

然後

(x*y)%A = ((int_x*A + mod_x)(int_y*A + mod_y))%A = (mod_x*mod_y)%A 

mod_x*mod_y要小很多，對不對？

編輯：

如果你正在努力尋找模WRT像10e11大一些，我想你將不得不使用另一種方法。不過，雖然沒有真正有效的，像這樣的工作

const int MAX_INT = 10e22 // get max int 

int larger = max(mod_x, mod_y) // get the larger number 
int smaller = max(mod_x, mod_y) 
int largest_part = floor(MAX_INT/smaller) 
if (largest_part > larger): 
    // no prob of overflow. use normal routine 
else: 
    int larger_array = [] 
    while(largest_part < larger): 
     larger_array.append(largest_part) 
     larger -= largest_part 
     largest_part = floor(MAX_INT/smaller) 

    // now use the parts array to calculate the mod by going through each elements mod and adding them etc 

如果你瞭解這個代碼和安裝程序，你應該能夠找出休息