c++ - 在 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应该小很多吧？

编辑：

如果你试图找到一个大数的模数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

如果您了解此代码和设置，您应该能够弄清楚其余的