Задача
Даны два взаимно простых натуральных числа [latex]a[/latex] и [latex]b[/latex]. Рассмотрим множество [latex]M[/latex] целых чисел, представимых в виде [latex][ax+by],[/latex]
где [latex]x[/latex] и [latex]y[/latex] — целые неотрицательные числа. Каково наибольшее целое число [latex]c[/latex], не принадлежащее множеству [latex]M[/latex]?
Входные данные
[latex]a[/latex] и [latex]b[/latex] — два взаимно простых натуральных числа.
Выходные данные
[latex]c[/latex] — наибольшее целое число c, не принадлежащее множеству [latex]M[/latex].
Тесты
| Входные данные |
Выходные данные |
| [latex]a[/latex] |
[latex]b[/latex] |
[latex]c[/latex] |
| 5 |
3 |
7 |
| 2 |
1 |
-1 |
| 3 |
2 |
1 |
Код программы на C++
|
|
#include <iostream> using namespace std; int main() { int a, b; cin >> a >> b; cout << a*b-a-b; return 0; } |
Код программы на Java
|
|
import java.util.*; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner scan = new Scanner(System.in); int a = scan.nextInt(); int b = scan.nextInt(); System.out.print(a*b-a-b); } } |
Решение
Нарисуем на плоскости систему координат [latex]Oxy[/latex] и сформулируем нашу задачу на геометрическом языке. Каждую пару целых чисел [latex]\left(x,y\right)[/latex] мы будем называть «целой точкой» и изображать красной точкой, если обе её координаты неотрицательны [latex]\left(x\geq0, y\geq0\right)[/latex], и синей точкой — если хотя бы одна координата отрицательна.
Взаимно простые натуральные числа [latex]a[/latex] и [latex]b[/latex] мы считаем фиксированными (для примера возьмём [latex]a=5, b=3[/latex]). Для каждого [latex]n[/latex] уравнение [latex]ax+by=n[/latex] определяет, как известно, прямую. Обозначим её через [latex]l_{n}[/latex]. Разумеется, все прямые [latex]l_{n}[/latex] параллельны друг другу. Пусть [latex]n[/latex] — целое. Будем считать прямую [latex]l_{n}[/latex] красной, если она проходит хотя бы через одну красную точку, и синей — в противном случае. Мы должны выяснить, каково наибольшее [latex]c[/latex], которому соответствует синяя прямая [latex]l_{с}[/latex], и доказать, что тогда из двух прямых [latex]l_{n}[/latex] и [latex]l_{c-n}[/latex] одна-синяя и одна-красная ([latex]n[/latex] — любое целое число).
Мы будем пользоваться в нашем решении перемещениями плоскости, которые отображают множество целых точек на себя и одновременно каждую прямую [latex]l_{n}[/latex] переводят в ту же самую или некоторую другую прямую [latex]l_{\acute{n}}[/latex] из нашего семейства. Это, во-первых, параллельные переносы на любой вектор [latex]\left(p, q\right)[/latex] с целыми [latex]p[/latex] и [latex]q:[/latex] [latex]\left(x,y\right)|\dashrightarrow \left(x+p, y+q\right),[/latex] и, во-вторых, повороты на [latex]180^{\circ}[/latex] (или, что то же самое, симетрии относительно точки) с любыми центрами [latex]\left(\frac{p}{2}, \frac{q}{2}\right)[/latex], где [latex]p[/latex] и [latex]q[/latex] — целые: [latex]\left(x,y\right)|\dashrightarrow \left(p-x, q-y\right).[/latex]
Докажем, что на каждой прямой [latex]l_{n}[/latex] целые точки встречаются через равные промежутки.
Лемма. Если [latex]\left(x_{0},y_{0}\right)[/latex] — целая точка на прямой [latex]l_{n}[/latex], то ближайшими к ней целыми точками на [latex]l_{n}[/latex] будут [latex]\left(x_{0}-b,y_{0}+a\right)[/latex] и [latex]\left(x_{0}+b,y_{0}-a\right)[/latex] ([latex]a[/latex] и [latex]b[/latex] взаимно просты).
Рассмотрим прямую [latex]l_{0}[/latex], проходящую через [latex]\left(0, 0\right)[/latex]. Пусть [latex]\left(-b_{1}, a_{1}\right)[/latex] — ближайшая к [latex]\left(0, 0\right)[/latex] целая точка [latex]l_{0}[/latex] такая, что [latex]b_{1}>0[/latex], [latex]a_{1}>0[/latex] (мы ещё не знаем, что [latex]b_{1}=b, a_{1}=a[/latex]), [latex]\left(x_{0}, y_{0}\right)[/latex] — целая точка [latex]l_{n}[/latex]. При переносе на вектор [latex]\left(x_{0}, y_{0}\right)[/latex] отрезок прямой [latex]l_{0}[/latex] от [latex]\left(0, 0\right)[/latex] до [latex]\left(-b_{1}, a_{1}\right)[/latex] перейдет в отрезок [latex]l_{n}[/latex] от [latex]\left(x_{0}, y_{0}\right)[/latex] до [latex]\left(x_{0}-b_{1}, y_{0}+a_{1}\right)[/latex] будет ближайшей к [latex]\left(x_{0}, y_{0}\right)[/latex] точкой [latex]l_{n}[/latex] сверху. Точно так же при переносе на вектор [latex]\left(x_{0}+b_{1}, y_{0}-a_{1}\right)[/latex] — тот же отрезок прямой [latex]l_{0}[/latex] перейдёт в отрезок прямой [latex]l_{n}[/latex] от [latex]\left(x_{0}+b_{1}, y_{0}-a_{1}\right)[/latex] до [latex]\left(x_{0}, y_{0}\right)[/latex]. Следовательно, и на этом отрезке целыми точками будут только его концы.
Отсюда уже следует, то на любой прямой [latex]l_{n}[/latex] (уесли на ней есть хоть одна целая точка) промежуток между соседними целыми точками один и тот же: [latex]a_{1}[/latex] единиц по оси [latex]Oy[/latex] и [latex]b_{1}[/latex] — по оси [latex]Ox[/latex]. Это, в частности, относится и к прямой [latex]l_{0}[/latex]. Поскольку [latex]\left(-b, a\right)[/latex] принадлежит [latex]l_{0}[/latex], то отсюда следует, что [latex]b=db_{1}, a=da_{1}[/latex], где [latex]d[/latex] — некоторое целое число. Но числа [latex]a[/latex] и [latex]b[/latex] по условию взаимно просты. Значит, [latex]d=1[/latex], то есть [latex]a=a_{1}, b=b_{1}[/latex]. Лемма доказана.
Из этой леммы следует, что каждая прямая [latex]l_{n}[/latex], где [latex]n[/latex] — целое, переходит ровно через одну точку внутри полосы [latex]0\leq x\leq b-1[/latex]. При этом, очевидно, если прямая красная, то есть где-то переходит через красную точку, то её целая точка в выделенной полосе тоже будет красной (а точка синей прямой, разумеется, синяя).
Теперь заметим, что при симетрии относительно точки [latex]\left(\frac{b-1}{2} -\frac{1}{2}\right)[/latex] [latex]\left(x,y\right)\mapsto\left(\acute{x}, \acute{y}\right) =\left(b-1-x, -1-y\right)[/latex], полоса [latex]0\leq x\leq b-1[/latex] переходит в себя, причем красные точки переходят в синие, и наоборот. Прямая [latex]l_{n}[/latex] после этой симметрии переходит в прямую [latex]l_{ab-a-b-n}[/latex]: если [latex]ax+by=n[/latex], то [latex]a\acute{x}+b\grave{y}=a\left(b-1-x\right)+b\left(-1-y\right)=ab-a-b-n.[/latex] (Через центр симметрии, где [latex]a\left( \frac{b-1}{2}\right)+b\left(- \frac{1}{2}\right) = \frac{ab-a-b}{2},[/latex] ни одна из наших прямых может и не проходить.)
Ясно, что самая нижняя красная прямая — это [latex]l_{0}[/latex]. Следовательно, самая верхняя синяя прямая — это [latex]l_{ab-a-b}.[/latex] Итак, наибольшее число, не принадлежащее множеству, — это [latex]c=ab-a-b,[/latex] и из двух чисел [latex]n[/latex] и [latex]c-n[/latex] одно принадлежит [latex]M[/latex], а другое — нет.
Ссылки
Ideone C++;
Ideone Java;
Решение задачи Журнал «Квант» №11 г.1973 (стр. 44-45);
Условие задачи Журнал «Квант» №3 г.1973 (стр. 35).
Related Images:
Для отправки комментария необходимо войти на сайт.