Как рассчитать (a * b * c * d/e)% m f 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). Опять же, я не могу взять модуль сначала? Что мне делать?

Answer 1

Использование модульных арифметических свойств и данных e divide a*b*c*d. Также предполагается, что m*m не переполняют тип используемых данных.

Как modular arithmetic состояние:

если 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 

дивизии не здесь. Таким образом вы можете не использование: ((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;