Задача на НОД,НОК

Вокруг звезды вращается n планет. Тангенциальная скорость планет постоянна. Направление вращений планет одинаково. Парадом планет называется момент времени, в который все планеты располагаются на одной прямой. Необходимо вычислить промежуток времени между последовательными парадами планет.За заданным количеством планет n вычислить n чисел – периоды вращения планет.

Создал алгоритм математически, но не знаю, как его реализовать на С++.
Такой вот алгоритм:Рассмотрим i - ую и j - ую планету. Они вместе с солнцем будут находиться на одной прямой через время t, если

Здесь через {x} обозначена дробная часть числа x.
Или то же самое, что значение

является целым. Поскольку i и j – любые значения от 1 до n, то можно утверждать, что число
K =
должно быть целым. Если в качестве t взять значение a / b, где
a = НОК(t1, t2, …, tn), b = 2 * НОД(t1 – t0, t2 – t0, …, tn – t0),
то значение K будет целым. Переменной t0 следует присвоить наименьшее значение из ti. Осталось сократить дробь a / b на их наибольший общий делитель.

Покажем, как вычислить a = НОК(t1, t2, …, tn), совершив минимум операций над большими числами (значение а является большим). Переберем все пары (ti, tj), i < j , для каждой пары вычислим d = НОД(ti, tj), после чего разделим tj на d. После этого произведение оставшихся ti равно значению а.

Изображения

 

0

Джон, вопрос-то в чем? То что нужно вычислить

Сообщение от Джон a = НОК(t1, t2, …, tn)

тут Вы правы.
А то как Вы это делаете:

Сообщение от Джон Переберем все пары (ti, tj), i < j , для каждой пары вычислим d = НОД(ti, tj), после чего разделим tj на d. После этого произведение оставшихся ti равно значению а.

не понятно.
Если вопрос именно в этом, то лучше в ручную распишите, как вычисляете НОК(3,4,5,6).
Также напишите максимально возможное n и ti.
Если есть ссылка на задачу, то лучше лучше укажите ссылку.

0

Эм, честно не уверен но вроде ссылки за форум разрешены.
Вообщем у меня на сайте есть функции для нахождения НОД и НОК,
можете поглядеть http://www.kolesnikov-dv.ru/?p=49 все с комментариями

0

Мне кажется, что здесь ещё формулы должны были быть, которые по каким-то причинам не отобразились.... Надо бы обновить

0

Сообщение от Джон Вокруг звезды вращается n планет. Тангенциальная скорость планет постоянна. Направление вращений планет одинаково. Парадом планет называется момент времени, в который все планеты располагаются на одной прямой. Необходимо вычислить промежуток времени между последовательными парадами планет.За заданным количеством планет n вычислить n чисел – периоды вращения планет. Создал алгоритм математически, но не знаю, как его реализовать на С++. Такой вот алгоритм:Рассмотрим i - ую и j - ую планету. Они вместе с солнцем будут находиться на одной прямой через время t, если Здесь через {x} обозначена дробная часть числа x. Или то же самое, что значение является целым. Поскольку i и j – любые значения от 1 до n, то можно утверждать, что число K = должно быть целым. Если в качестве t взять значение a / b, где a = НОК(t1, t2, …, tn), b = 2 * НОД(t1 – t0, t2 – t0, …, tn – t0), то значение K будет целым. Переменной t0 следует присвоить наименьшее значение из ti. Осталось сократить дробь a / b на их наибольший общий делитель. Покажем, как вычислить a = НОК(t1, t2, …, tn), совершив минимум операций над большими числами (значение а является большим). Переберем все пары (ti, tj), i < j , для каждой пары вычислим d = НОД(ti, tj), после чего разделим tj на d. После этого произведение оставшихся ti равно значению а.

во первых:слишком много пар сравнивается, во вторых: так нельзя НОК всех чисел найти
1) НОК (a,b,c,d,e ...) = НОК( НОК(a,b) , c,d,e ...) или НОК ( НОК(a,b), НОК(c,d,e ...))
2) если планеты i,j - на одной линии с солнцем, i,k - на одной линии с солнцем, тогда j,k на одной линии с солнцем и их не надо проверять
т.е. достаточно выбрать жертву(допустим ближайшая планета), а остальные должны быть на одной линии с ней и с солнцем

т.е. алгоритм совсем простой
надо найти HOK(L,t2-t1,t3-t1,...,tn-t1),
L-Pi радиан или 180° или 200 градиан или что там еще?

0

Так выглядит задача, если я как-то неправильно поставил ее условие.
http://www.e-olimp.com.ua/problems/1185

0

Сообщение от Джон Так выглядит задача, если я как-то неправильно поставил ее условие. http://www.e-olimp.com.ua/problems/1185

теперь я даже не представляю что ты там писал, есть кстати предпросмотр когда мессдж отправляешь
вот в цитате предыдущей видно, что ты запостил, и не видно, что ты хотел этим сказать
после всяких "если" "значение" "К=" следует пустота

0