Задача взята с сайта 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$.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
include <iostream> unsigned long long mult(unsigned long long x,unsigned long long y,unsigned long long const z){ if(y == 1)return x % z; else if(y == 0)return 0; else if( y & 1 )return (x % z + mult(x % z,(y - 1) % z,z))%z; else return mult((x + x)%z,(y / 2) % z,z); } int main() { unsigned long long a,b,c; std::cin >> a >> b >> c; std::cout << mult(a,b,c); } |
Хорошо получилось.
Немного лишних остатков от деления для перестраховки, но не страшно.
Пожалуй стоит поменять местами возвращаемые значения в 5-й и 6-й строках, чтобы не писать отрицание в условии.
Только обязательно исправьте или уберите ссылку в начале — она ведёт на Вашу предыдущую задачу.