在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 

如果你了解这个代码和安装程序，你应该能够找出休息