2

Добрый день!

В решении своей задачи мне необходимо находить остаток от деления произведения чисел. Формально это можно записать так:

x = (a * b) mod c, где a, b и с - целые положительные числа, и с > a.

Дело в том, что при реализации этого этапа задачи на языке программирования (пишу на C#) будет происходить переполнение целочисленного типа при значениях >50 000 (Int32).

На языке C# это выражение у меня выглядит так:

x = (a * b) % c;

Вопрос: Существует ли формула, позволяющая разбить вышеописанную формулу на выражение с двумя mod'ами или существует ли способ, позволяющий как-то избежать вычисления произведения двух больших чисел? Благодарю.

rugabarbo
  • 1,317
  • 6
  • 22
Andrei Khotko
  • 5,035
  • Может использовать Int64 – diralik Sep 10 '17 at 15:05
  • @diraria это как вариант, но вопрос не в этом. Я просто не хотел бы работать с Int64, поэтому хотел узнать, существует ли формула, упрощающая вычисление. – Andrei Khotko Sep 10 '17 at 15:06
  • @diraria что-то вроде (a + b) / c = a/c + b/c – Andrei Khotko Sep 10 '17 at 15:08
  • @diraria нет, это уж слишком для вычисления одной формулы) У меня в программе такая формула вычисляется около 50 000 раз:) а там еще помимо этого поиск в списке такого же размера. – Andrei Khotko Sep 10 '17 at 15:35
  • Ну я всё равно напишу, почти дописал уже – diralik Sep 10 '17 at 15:36
  • @diraria хорошо, все же интересно взглянуть на это решение :) – Andrei Khotko Sep 10 '17 at 15:38

3 Answers3

4
(a * b) mod c = ((a mod c) * (b mod c)) mod c
rugabarbo
  • 1,317
  • 6
  • 22
  • А если a=50000, b=50000, c=10^9+7? – diralik Sep 10 '17 at 15:26
  • Да, это то, что я хотел, благодарю! :) Но я тут подумал, что это мне не поможет избежать переполнения, если a < c и b < c. Но за формулу спасибо – Andrei Khotko Sep 10 '17 at 15:27
  • Вопрос автора состоит в том, существует ли формула. Ответ дан. – rugabarbo Sep 10 '17 at 15:27
4

Прагматическое решение — используйте для умножения число большей разрядности, в вашем случае — ulong. Произведение двух положительных int'ов всегда помещается в ulong, поэтому при вычислении произведения переполнения не произойдёт. Однако, следите, чтобы ваши исходные числа были положительными.

Заметьте, что оператор % имеет смысл использовать только для положительных чисел, для отрицательных он ведёт себя странно, поэтому для приведения числа к промежутку [0, c) вам придётся отдельно рассматривать знак числа.

VladD
  • 206,799
3

Ещё можно по аналогии с алгоритмом быстрого возведения в степень по модулю.

Работает за O(log b), но зато корректно вычисляет для a=50000, b=50000, c=10^9+7:

  • Пусть b = 2k + r, где r это 0 либо 1.
  • Тогда a * b = a * (2k + r) = a * 2k + a * r = 2a * k + (a или 0)
  • Таким образом, мы свели задачу умножения двух чисел к задачам
    • умножение числа на два
    • умножение двух чисел (но второе число в этот раз меньше в два раза)
    • сложение двух чисел

Код на C++ (Ideone): 

int multiply(int a, int b, int mod) {
    if (b == 0) {
        // a * 0 = 0
        return 0;
    } else {
        // b = 2k + r
        int k = b / 2;
        int r = b % 2;

        // a * (2k + r) = 2a * k + a * r
        return (multiply(a * 2 % mod, k, mod) + a * r) % mod;
    }
}
diralik
  • 9,395