e-olymp 4752.  Кинотеатр

Задача

Однажды, ученики B-й школы города G решили съездить в кино. Администрация кинотеатра расположила их в зале размера $n × m$, который специально был подобран так, чтобы все места были заняты школьниками. Каждому посетителю кинотеатра был выдан свой номер.

Школьники заняли свои места следующим образом: они входили в зал в порядке, в котором шли их номера, и полностью занимали сначала первый ряд, потом второй, потом третий и т.д.

Однако классный руководитель решил, что такая рассадка плохо влияет на поведение учащихся и пересадил их по-другому: ученики сначала занимали все первые места каждого ряда, потом все вторые места каждого ряда и т.д. (см. рисунок).

Администрация решила выяснить, сколько учащихся не поменяют своего места после пересадки.

Входные данные:
В первой строке заданы числа $n$ и $m$ $(1 \le n, \le 1000)$.

Выходные данные:
Выведите одно число — количество учеников, которые в результате пересадки останутся сидеть на тех же местах.

Тесты

Входные данные Вывод программы
3 3 3
3 2 2
231 543 3

Решение

Введем координаты: $x$ слева направо с нуля, $y$ снизу вверх с нуля.
В первой рассадке на месте $(x, y)$ сидит ученик $ny + x + 1$, во второй рассадке на этом месте сидит ученик $mx + y + 1$. Элементарными преобразованиями сводим нашу задачу к задаче посчитать количество решений уравнения в натуральных числах $ \frac{x}{y} = \frac{n — 1}{m — 1} $, не забыв прибавить единицу для решения $(0, 0)$. Таких пар $(x, y)$ существует ровно $gcd(n — 1, m — 1)$, так как нам нужно найти количество возможных сокращений дроби $\frac{n — 1}{m — 1}$.

Для поиска НОД воспользуемся алгоритмом Евклида.

Код (Рекурсия)

Код (Цикл)

Ссылки

Задача на E-Olymp
Код на IdeOne
Засчитанное решение на E-Olymp

Добавить комментарий