1033. Торт от Толи

Толя на день рождения собирается угостить друзей тортом. Известно, что на дне рождения может быть либо n, либо m человек, включая самого именинника. На какое минимальное количество частей ему нужно разрезать торт (не обязательно всех равных), чтобы при любом из указанных количестве собравшихся, все съели торт поровну?

Вход. Два числа m и n (1 ≤ m, n ≤ 30000).

Выход. Вывести искомое минимальное количество кусочков торта.

Пример входа	Пример выхода
2 3	4

РЕШЕНИЕ

НОД

Анализ алгоритма

Представим торт в виде отрезка некоторой длины. Отметим на нем разрезы в случае разделения на n равных частей. Затем отметим на нем разрезы в случае разделения на m равных частей. Совершим отмеченные разрезы – они и будут искомыми. Осталось подсчитать количество частей, на которое распадется отрезок. Это количество будет равно

n + m – НОД(n, m)

Доказательство. Количество разрезов, которые делят торт на n равных частей, равно n – 1. Количество разрезов, которые делят торт на m равных частей, равно m – 1. Среди них будет НОД(n, m) – 1 совпадающих разрезов. Итого имеем на торте (n – 1) + (m – 1) – (НОД(n, m) – 1) = n + m – 1 – НОД(n, m) разных разрезов. После их совершения торт распадется на n + m – НОД(n, m) кусков.

Пример

При разрезании торта на 6 частей имеем 5 разрезов.

При разрезании торта на 9 частей имеем 8 разрезов.

НОД(6, 9) – 1 = 2 разрезов совпадают.

Итого на торте имеется 5 + 8 – 2 = 11 разных разрезов. После их совершения торт распадется на 12 кусков.

Реализация алгоритма

Функция gcd возвращает наибольший общий делитель чисел a и b.

int gcd(int a, int b)

{

return (!b) ? a : gcd(b,a % b);

}

Основная часть программы. Читаем входные данные.

scanf("%d %d",&m,&n);

Вычисляем и выводим ответ.

res = m + n - gcd(m,n);

printf("%d\n",res);

Java реализация

import java.util.*;

public class Main

{

Функция gcd возвращает наибольший общий делитель чисел a и b.

static int gcd(int a, int b)

{

return (b == 0) ? a : gcd(b,a % b);

}

public static void main(String []args)

{

Читаем входные данные.

Scanner con = new Scanner(System.in);

int m = con.nextInt();

int n = con.nextInt();

Вычисляем и выводим ответ.

int res = m + n - gcd(m,n);

System.out.println(res);

con.close();

}

}

Python реализация

Функция gcd возвращает наибольший общий делитель чисел a и b.

def gcd(a, b):

if a == 0: return b

if b == 0: return a

if a > b: return gcd(a % b, b)

return gcd(a, b % a)

Читаем входные данные.

m, n = map(int, input().split())

Вычисляем и выводим ответ.

res = m + n - gcd(m, n)

print(res)