e-olymp 8654. Целочисленное умножение

Задача взята с сайта e-olymp

Задача

Даны три целых числа $a, b, c.$ Вычислить значение выражения $a \cdot b \text{ mod } c.$

Входные данные

Три целых положительных числа $a, b, c \left( a, b, c < 2^{63} \right).$

Выходные данные

Вывести значение выражения $ a \cdot b \text{ mod } c.$

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 2 3 2 0
2 11 3 2 1
3 123456789
987654321
17
0
4 5000400000023
23000400400500
100000000070707
68238553233174
5 10000018585
10000000000005
101020304050607080
85850050000993845

Решение

Для решения задачи напишем рекурсивную функцию умножения, основанную на том, что [latex]\displaystyle a\cdot b =\displaystyle[/latex][latex] \begin{cases}\left(a+a\right)\cdot\frac{b}{2} &\text{} b\equiv_{2} 0 \\a+a\cdot\left(b-1\right) &  \text{} b \not \equiv_{2} 0\ \end{cases}.[/latex] Поскольку максимальное значение из условия задачи в два раза меньше максимального числа из 64-битных беззнаковых чисел и[latex]\left(a\cdot b\right)\text{ mod } c =\left(a\text{ mod } с \cdot b\text { mod }c\right)\text{ mod }c,[/latex] мы можем на каждом шагу применять к $a$ и $b$  операцию остатка от деления на $c$ , за счет чего произведение никогда не будет превосходить $2^{64}-1$.

  • Засчитанное решение на e-olymp
  • Код на ideone

One thought on “e-olymp 8654. Целочисленное умножение

  1. Хорошо получилось.
    Немного лишних остатков от деления для перестраховки, но не страшно.
    Пожалуй стоит поменять местами возвращаемые значения в 5-й и 6-й строках, чтобы не писать отрицание в условии.
    Только обязательно исправьте или уберите ссылку в начале — она ведёт на Вашу предыдущую задачу.

Добавить комментарий