Задача
Однажды, ученики 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}$.
Для поиска НОД воспользуемся алгоритмом Евклида.
Код (Рекурсия)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <iostream> using namespace std; int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); } int main() { int n, m; cin >> n >> m; cout << gcd(n - 1, m - 1) + 1 << endl; return 0; } |
Код (Цикл)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> using namespace std; int gcd(int a, int b) { while (b != 0) { int t = a % b; a = b; b = t; } return a; } int main() { int n, m; cin >> n >> m; cout << gcd(n - 1, m - 1) + 1 << endl; return 0; } |
Ссылки
Задача на E-Olymp
Код на IdeOne
Засчитанное решение на E-Olymp