如何计算 (a*b*c*d/e)%m，其中 a、b、c、d、e 的数量级为10^18？

Question

我想计算 (a*b*c*d/e)%m，其中我的 a,b,c,d,e 都是 10^18 级别的数。 e 完全能够整除 a*b*c*d。问题是我不能先将它们相乘，因为我无法存储它们，因为它们的范围会达到 10^72。同样，我也不能先取模？我该怎么办？

- user3868494

---

为什么您不能先取模数？ - Stephen Canon

@StephenCanon 我觉得我不能先取模，因为 (a/b)modc 不等于 (a mod c)/(b mod c)。 - user3868494

@Kevin，对我来说，转换到Python不是一个选项。 :) - user3868494

@user3868494：但是a/b等同于a*(1/b)，而且(a*c)%m == ((a%m)*(c%m))%m。 - Joel Cornett

“1/b”不是整数，“(ac)%m == ((a%m)(c%m))%m”这个等式只在“a”和“c”为整数时才有意义。通过对模“m”取乘法逆元，可以使你所说的内容正确，但这可能不存在且计算不简单。 - interjay

m的大小是多少？ - miracle173

Answer 1

使用模算术特性并且 e 整除 a*b*c*d。同时假设在数据类型中，m*m 不会溢出。

根据模算术的规则：

如果 a1 = b1 mod n 且 a2 = b2 mod n，那么：

a1 + a2 = b1 + b2 mod n
a1 - a2 = b1 - b2 mod n
a1 * a2 = b1 * b2 mod n

这里没有“division”（除法）运算符。因此，你不能使用以下代码：((a%m)*(b%m)*(c%m)*(d%m)/(e%m))%m

代码。

gcd_value = gcd(a, e);
result = (a / gcd_value) % m;
e /= gcd_value;
gcd_value = gcd(b, e);
result *= (b / gcd_value) % m;
e /= gcd_value;
gcd_value = gcd(c, e);
result *= (c / gcd_value) % m;
e /= gcd_value;
gcd_value = gcd(d, e);
result *= (d / gcd_value) % m;
result = result % m;

- NetVipeC