переполнение — поиск остатка большого умножения в переполнении стека

Я хотел бы попросить некоторую помощь относительно следующей проблемы. Мне нужно создать функцию, которая будет умножать два целых числа и извлекать остаток от этого умножения, деленный на определенное число (короче, (x * y)% A).

Я использую unsigned long long int для этой проблемы, но A = 15! в этом случае и x, и y были вычислены по модулю A ранее. Таким образом, x * y может быть больше 2 ^ 64 — 1, поэтому переполняется.

Я не хотел использовать внешние библиотеки. Может ли кто-нибудь помочь мне разработать короткий алгоритм для решения этой проблемы?

Заранее спасибо.

1

Решение

Если у вас уже есть мод A из x и y, почему бы не использовать их? что-то вроде,

если,

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

Если вы понимаете этот код и настройки, вы сможете выяснить остальные

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]