Составьте программу mulmod.c, вычисляющую выражение (a ⋅ b) mod m, то есть остаток от деления произведения чисел a и b на m.

[email protected] в категроии Информатика, вопрос открыт 17.10.2017 в 02:19

Известно, что a, b и m – натуральные числа, меньшие, чем 263, причем m ⁄= 0. Программа должна считывать из стандартного потока ввода числа a, b и m и выводить результат в стандартный поток вывода.
Основная сложность этой задачи заключается в том, что произведение a на b может превышать 264 и, тем самым, не помещаться ни в один из целочисленных типов данных языка C. При этом представление формулы в виде ((a mod m ) ⋅ (b mod m )) mod m тоже не решает проблемы, так как при больших значениях m произведение (a mod m ) ⋅ (b mod m ) тоже может превышать 264.
Решение этой задачи сводится к вычислению значения полинома по схеме Горнера. Представим число b в двоичной системе счисления: -------------
b = b63b62...b1b0. Здесь b63,b62, ...,b1,b0 – двоичные разряды, формирующие число, то есть

b = b63 ⋅ 263 + b62 ⋅ 262 + ...+ b1 ⋅ 2 + b0.
Тогда

[ ]
(a ⋅ b) mod m = a ⋅ b63 ⋅ 263 + a ⋅ b62 ⋅ 262 + ...+ a ⋅ b1 ⋅ 2 + a ⋅ b0 mod m.
Преобразовав это выражение по схеме Горнера, получим

(a ⋅ b) mod m = [(...(a ⋅ b63 ⋅ 2 + a ⋅ b62) ⋅ 2 + ...+ a ⋅ b1) ⋅ 2 + a ⋅ b0] mod m.
(1)
Учитывая, что для любых x, y и m ⁄= 0 справедливы тождества

(x + y) mod m ≡ ((x mod m ) + (y mod m )) mod m,
(x ⋅ y) mod m ≡ ((x mod m ) ⋅ (y mod m )) mod m,
мы имеем право при вычислении правой части формулы 1 поступать следующим образом: если есть возможность того, что сумма двух слагаемых превзойдёт 264, нужно складывать остатки от деления этих слагаемых на m; аналогично для произведения. Этот приём даёт гарантию того, что при вычислении ни разу не произойдёт переполнение.