Целые решения линейного уравнения в границах
Точное число целых пар ax + by = c внутри заданных границ, параметрическое семейство и до ста показанных решений.
Ваш пример
Разбор примера
Подходящих пар: 2
| x | y |
|---|---|
| 2 | 2 |
| 5 | 0 |
- НОД(|a|,|b|)=3.
- Частное решение: x₀=-10, y₀=10.
- Все целые решения: x=-10+(3)t, y=10+(-2)t.
- Оставляем только целые t, удовлетворяющие обеим включённым границам.
- Всего решений
- 2
- Показано пар
- 2
- Остальные
- 0
Метод и условия расчёта
Расширенный алгоритм Евклида даёт частное решение. Семейство x=x₀+(b/g)t, y=y₀−(a/g)t пересекается с целочисленными границами.
Вопросы по теме
Программа перебирает весь большой прямоугольник?
Нет. Число решений вычисляется по границам параметра; вывод ограничен ста парами.
Можно ввести нулевой коэффициент?
Да. Уравнение с одним нулём и случай a=b=0 рассматриваются отдельно; конечные границы обязательны.
Теория чисел: углубление: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.