Task 62. Подарки
UniLecsЗадача: детям на новый год раздавали пакеты с подарками, в каждый пакет раскладывали апельсины.
Сначала разложили апельсины по m штук в каждый пакет, но не получилось, на один из пакетов пришелся m-1 апельсин. Когда попробовали положить по m-1 апельсина, то осталось m-2. Попробовали разложить по m-2 апельсина, осталось m-3. Попробовали положить по 2 апельсина, остался 1.
Нужно выяснить какое кол-во апельсинов изначально было.
Входные данные: m - кол-во апельсинов (1 < m <= 1000), ктр изначально планировали разложить по подаркам.
Вывод: Наименьшее возможное кол-во апельсинов, ктр были изначально.
Пример:
m - 4
Вывод: 11.
Идея: по сути ответом в задаче будет значение а=НОК(1, 2, 3, ..., m)-1.
При делении числа a на i(2<=i<=m) в остатке будет i-1, как и должно быть по условию.
Разберем как можно вычислить значение а=НОК(k1, k2, ..., k3). Переберем все пары (ki, kj), i<j, для каждой пары вычислим d=НОД(ki, kj), после чего разделим kj на d. После этого произведение оставшихся ki равно значению a.
Реализация:
Так как значения при вычислениях НОК (Наименьшее общее кратное) могут быть большими, воспользуемся длинной арифметикой, в C# для этого есть специальный класс BigInteger.
https://gist.github.com/unilecs/16b234ded7a306614581a81511941192
Тест: