#FaangTalk 73 - Линейные диофантовы уравнения для алго-интервью

В гостях Anonymous FAANG Engineer Решение уравнения 2x-5y=19 (про шоколадку). https://telegra.ph/Reshenie-uravneniya-2x-5y19-pro-shokoladku-01-20 Chapters 00:00 Введение в системдизайн и алгоритмические интервью 01:01 Алгоритм Евклида и линейные диафантовые уравнения 03:44 Общие понятия: наибольший общий делитель и наименьшее общее кратное 08:05 Применение алгоритма Евклида в программировании 10:28 Доказательство алгоритма Евклида 15:05 Делители и остатки в алгоритме Евклида 17:33 Делители и их свойства 20:36 Наибольший общий делитель 24:30 Расширение на целые числа 29:21 Положительные и отрицательные остатки 31:15 Применение формул для нахождения GCD 32:36 Имплементация алгоритмов и их применение 34:02 Проектирование систем: пример светофора 36:08 Наибольший общий делитель и его применение 39:59 Проверка условий для нахождения НОД 41:52 Значение доказательств в алгоритмах 46:01 Переход к наименьшему общему кратному 51:24 Жизненные примеры диафантовых уравнений 54:14 Рациональные и иррациональные числа в уравнениях 56:51 Необходимые условия для существования решений 01:00:10 Общее решение диафантовых уравнений 01:03:29 Дельта x и дельта y для уравнений 01:06:13 Доказательства и их необходимость 01:09:36 Общая форма решений уравнений 01:11:44 Частные решения и их вычисление 01:16:10 Итеративные методы и алгоритмы 01:19:38 Общие решения для целых чисел 01:20:07 Заключение и алгоритмы 01:21:04 Итерация алгоритма Евклида 01:29:09 Обсуждение и завершение