Task 94. Пирог

Задача: был приготовлен большой пирог на семейный праздник. К вам придут N гостей, но возможно, к вам заедут еще и старые друзья и тогда гостей будет M человек, включая вас. 

На какое минимальное кол-во частей вам необходимо разрезать пирог (не обязательно всех равных), чтобы при любом кол-ве гостей, все сьели пирог поровну?

Входные данные: N, M, где N,M меньше 10000

Вывод: минимальное кол-во кусочков пирога

Пример: 

N = 2, M = 3

Answer: 4

Идея: давайте условно развернем пирог в виде отрезка. И отметим на нем куски в случае разделения на N равных частей. Далее отметим куски в случае разделения на M равных частей. Отмеченные куски и будут искомыми. Нужно только подсчитать кол-во таких частей, на ктр делится условный отрезок. Это кол-во будет равно:

N + M - НОД(N, M)

где НОД(N, M) - наибольший общий делитель чисел N и M.

Рассмотрим наш пример:

N = 2, M = 3

Реализация:

https://gist.github.com/unilecs/40abdf42f61037da5c0e4e4a7e7d62e3

Test:

https://dotnetfiddle.net/yzO8IV