a*b mod m

a*b mod c = (a mod c) * (b mod c) mod c

И вообще, что на алгебру в универе ходить не модно стало?

Обычная группа вычетов по модулю m. Или я что-то путаю?

Хм, а если (a mod c) * (b mod c) в 32 бита не влазит?

ну это в общем-то и происходит. и пары я не прогуливал. Тут скорее не математическая задача. Нужен некий алгоритмический трюк.

Уважаемый alexru!

А вы можете озвучить выражение a*b mod m ?

Ибо деление по модулю/кольца вычетов не есть mod или % в языках программирования...

>Есть 3 32 разрядных числа a, b и m. Можно-ли вычислить значение выражения a*b mod m, не выходя за рамки 32-разрядных чисел?

Первое, что приходит на ум - взять двоичное разложение b

b = sum(b_i * 2^i, i=0..N);

тогда (a*b) mod c = sum(a*b_i*(2^i) mod c, i=0..N)

a*(2^i) mod c = ((a*2 mod c)*2 mod c)...

a*b mod m = (a*(b mod 2) mod m + 2*(a*(b div 2) mod m)) mod m

Не знал таких тонкостей.

Нужно выполнить сишную операцию (a*b) % m. В 32-х разрядных числах.

Записал это на си так: (a*(b % 2) % m + 2*(a*(b>>1) % m)) % m. Сходу не заработало. Как получилось это выражение ?

Формула судя по всему верная (на калькуляторк все сходится), но тоже переполняется.

a*(b>>1) % m надо рекурсивно считать

> пары я не прогуливал

> Формула судя по всему верная (на калькуляторк все сходится)

мдяяя

Я догадался. Спасибо.