Загоны для скота — разбор задачи

1. Идея

Нужно найти максимальный размер загона, чтобы:

• каждый загон содержал одинаковое число животных;
• в одном загоне были животные только одного вида;
• все a животных первого вида и все b животных второго вида распределялись без остатка.

Это означает, что размер загона должен делить и число a, и число b.

Значит, требуется найти наибольшее общее число, на которое делятся оба числа. Это и есть НОД — наибольший общий делитель.

2. Наблюдения

Наблюдение 1

Если размер загона равен x, то:

• a должно делиться на x,
• b должно делиться на x.

То есть x — общий делитель чисел a и b.

Наблюдение 2

Нужен не просто общий делитель, а максимальный. Значит, ответ — это gcd(a, b).

Наблюдение 3

Для нахождения НОД очень удобно использовать алгоритм Евклида:

• пока b != 0,
• заменяем (a, b) на (b, a % b).

Когда b станет равным 0, в a будет храниться НОД.

3. Алгоритм

1. Считать a и b.
2. Пока b не равно 0:
   • вычислить остаток a % b,
   • присвоить a = b,
   • присвоить b = остаток.
3. Вывести a.

4. Почему это работает

Основа решения — свойство НОД:

• gcd(a, b) = gcd(b, a % b).

Почему это верно?

Если число d делит и a, и b, то оно делит и a - k * b, где k — любое целое число. В частности, оно делит остаток от деления a на b, то есть a % b.

И наоборот, если число делит b и a % b, то оно делит и a, потому что:

a = (a / b) * b + (a % b).

Значит, множество общих делителей у пар (a, b) и (b, a % b) одинаково, а значит, одинаков и их наибольший общий делитель.

Мы повторяем это преобразование, пока второе число не станет нулём. Когда получаем пару (a, 0), НОД равен a, потому что:

• любое число делит 0,
• значит, наибольший общий делитель чисел a и 0 — это a.

Следовательно, алгоритм действительно находит ответ.

5. Сложность

Алгоритм Евклида работает очень быстро:

• по времени: O(log(min(a, b))),
• по памяти: O(1).

Это легко укладывается в ограничения даже при a, b до 10^18.

6. Код на C++17

#include <iostream>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;

    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }

    cout << a << "\n";
    return 0;
}

7. Код на Python 3

a, b = map(int, input().split())

while b != 0:
    a, b = b, a % b

print(a)