如何计算（A * B * C * D / E）％的MFA，B，C，D，E是为了10 ^ 18？ [英] How to calculate (a*b*c*d/e)%m f a,b,c,d,e are of order 10^18?

问题描述

我要计算（A * B * C * D / E），％M 在我的 A，B，C，D，E 是为了 10 ^ 18 。 电子完全分裂 A * B * C * D 。问题是，我无法将它们相乘，因为我将无法保存他们，因为他们将是范围（10 ^ 72）的。同样，我不能拿模第一任？我该怎么办？

I want to calculate (a*b*c*d/e)%m where my a,b,c,d,e are of order 10^18 . e perfectly divides a*b*c*d. The problem is that I cannot multiply them, as I won't be able to store them as they would be of the range(10^72). Again, I can't take modulus first either? What should I do?

推荐答案

使用模运算属性和电子隔膜 A * B * C * D 。同时假定 m * m的不会溢出所使用的数据类型。

Using the modular arithmetic properties and that e divide a*b*c*d. Also assuming that m*m don't overflow in the type of data used.

由于模运算状态：

如果 A1 = B1模N 和 A2 = B2模N 则：

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

在师是不是在这里。通过这一点，你可以的不可以使用：（（A％M）*（B％M）*（C％M）*（D％M）/（E＆M） ）％M

The division is not here. By this you could not use: ((a%m)*(b%m)*(c%m)*(d%m)/(e%m))%m

code。

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;

这篇关于如何计算（A * B * C * D / E）％的MFA，B，C，D，E是为了10 ^ 18？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！