Как вычислить этот модуль при переполнении целого числа

Question

(10^{17}-1)*(10^{17}-1) mod 10^{18} 

Я решаю проблему программирования, и я держу свои целые числа в целых числах длиной 64 бит. Выше - это конкретный случай, который я не могу решить. (ab) mod m = (a mod m) (b mod m) mod m, здесь не выполняется (mod m) (b mod m) будет по-прежнему переполнять 64-битное целое число. Как я могу это решить? Я использовал только 17-ю силу. Проблема сохраняется даже для всех целых чисел в диапазоне (10^{10}, 10^{18} -1).

Редактировать: Я использую C++ для решения этой проблемы. Эта проблема может быть решена без использования библиотеки для обработки больших целых чисел.

Answer 1

Вы можете использовать личность, указанную вами, вам просто нужна другая аналогичная идентификация: (a+b) mod m = (a mod m) + (b mod m).

Цель состоит в том, чтобы умножить x*y mod m без каких-либо промежуточных значений, превышающих предел переполнения (в данном случае 2^64), где x начинает меньше m (если это не так, уменьшить ее моды m), y возможно больше m и x*y может потенциально переполняться. Мы можем это сделать, если m меньше половины предела переполнения.

Решение просто: просто выполните базовое умножение по битам для x*y и выполните каждый шаг по модулю m.

Начинается с x и y менее m (если это не так, уменьшите его сначала). Напишите y в форме a_0 * 2^0 + a_1 * 2^1 + a_2 * 2^2 + ..., где a_n либо 0, либо 1 (с указанием присутствующего термина или нет). (. Ака, написать y в двоичной форме) Теперь мы имеем:

x * (a_0 * 2^0 + a_1 * 2^1 + a_2 * 2^2 + ...) mod m 

Распределить x по каждому из условий y:

(x * a_0 * 2^0) + (x * a_1 * 2^1) + (x * a_2 * 2^2) + ... mod m 

Затем используйте оригинальную идентичность умножения: Для каждого термина выше, умножьте x на 2 mod m, пока вы не достигнете желаемой мощности 2 для этого срока. (Начиная с x < m и 2 * m < 2^64, затем 2 * x < 2^64, поэтому мы можем умножить на 2 без переполнения.) Когда вы закончите, добавьте результат для каждого термина mod m (вы можете сохранить текущую сумму по ходу дела).

Ни одна из этих операций не превысит 2^64 и, следовательно, не будет переполняться. Это будет работать для любого значения m менее 2^64/2 = 2^63 и любых целых чисел x и y менее m.

Это не обязательно самый быстрый способ сделать это, не стесняйтесь находить что-то более эффективное. Во-первых, меньший m сравнивается с лимитом переполнения, чем больше оснований для условий, которые мы можем переписать y as.