eolymp
bolt
Try our new interface for solving problems
Məsələlər

Слоны на торовидной доске

Слоны на торовидной доске

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Слон - это шахматная фигура, которая может передвигаться по диагонали на любое количество клеток.

Представьте себе, что мы возьмем доску размером mхn и соединим ее верхний и нижний край, а также левый с правым, в результате чего доска примет форму тора. Например, для доски 7×10 соседями клетки (4, 1) будут (3, 10), (3, 1), (3, 2), (4, 10), (4, 2), (5, 10), (5, 1), (5, 2); соседями клетки (1, 10) будут (7, 9), (7, 10), (7, 1), (1, 9), (1, 1), (2, 9), (2, 10), (2, 1).

На торовидной доске шахматные фигуры не ограничены ее размерами, и например, на доске 7×10 слон может пойти из любой клетки в любую другую за один ход. Например, из клетки (2, 1) в клетку (7, 9) ведет путь (2, 1) (1, 10) (7, 9).

Будем говорить, что множество слонов покрывают доску, если всегда можно передвинуть какого-нибудь слона в любую пустую клетку за один ход. Другими словами, каждая клетка доски либо занята, либо находится под боем некоторого слона.

Вам следует найти наименьшее количество слонов, которыми можно покрыть торовидную доску m×n.

Giriş verilənləri

Два числа m и n (1 n, m 10^100).

Çıxış verilənləri

Вывести наименьшее количество слонов, которыми можно покрыть торовидную доску размера m×n.

Nümunə

Giriş verilənləri #1
2 2
Çıxış verilənləri #1
2
Mənbə 2004 Петрозаводск, Лето, Контест Андрея Станкевича 7, Август 22, Задача I