Всем привет! Извините за столь для большинства программистов "нубский" вопрос: "Как найти НОК нескольких чисел?" Если это НОД, то думаю все понятно. Но так как НОК можно найти с помощью деления произведения всех чисел на НОД, произведение всех чисел может выйти за пределы 64-битных чисел. Вот и возник вопрос как это сделать?
Решал задачу с Казахстанкой олимпиады 2013г. Ссылка на условия (Задача С).
P.S: Кому не лень, напишите решение.
НОК(a, b) = a / НОД(a,b) * b
НОК(а1, a2, ... an) = НОК(a_1, ... a_{n-2}, НОК(a_{n — 1}, a_n)$
Промежуточные вычисления не больше ответа
А зачем в этой задаче явно находить НОК, если можно найти его факторизацию?
Можно подробнее?
Ну если разложить каждое число на простые множители, разложение их НОКа можно получить, просто взяв максимальную степень по каждому из простых множителей среди всех чисел.
А как все таки решить эту задачу ?
Для N<=20 должен проходить перебор по маскам, а вот для N<=60 я пока что не придумал ничего лучше, чем перебор по простым множителям НОК. Я не уверен, но мне кажется, что количество возможных вариантов НОК достаточно малО. После того, как НОК был зафиксирован, задача сводится к комбинаторной.
Да, я туплю — легко показать, что НОК для игроков определяется однозначно и равен НОК всех чисел. Если бы у нас не было чисел с простыми множителями, превышающими 23 (это 9-е простое число), можно было бы решить задачу динамикой dp[k][mask1][mask2], где k — количество чисел, которые мы уже просмотрели, mask1 и mask2 — маски для 1-го и 2-го игрока соответственно, где i-й бит равен 1 тогда и только тогда, когда i-е простое число для соответствующего игрока мы уже взяли в той степени, в которой оно содержится в НОК. В динамике хранится количество способов получить такую позицию, переходы динамики — "дать следующее число 1-му игроку" и "дать следующее число 2-му игроку". Пусть такие числа есть. Заметим, что они представимы в виде p*x, где p — простое число превышающее 23, а x<=6 (так как числа не превосходят 160). Очевидно, число p может входить только со степенью 1, а x может влиять лишь на степень первых трех простых чисел (2, 3, 5). Перебирая все возможные пары масок длины 3, находим (комбинаторно) количество способов разделить числа вида p*x между игроками с такой парой масок, после чего для каждой из этих пар находим все пары масок из динамики, которые дополняют их до единичных, и перемножаем результаты.
Это утверждение неверно. Общая формула имеет такой вид.
[a1, a2, ..., an] — НОК чисел,
(a1, a2, ..., an) — соответственно, НОД.
Но вообще лучше пользоваться тем, что НОК — ассоциативная операция и просто вычислять его последовательно.