e-olymp 8362. Множители

Задача

Найти число от $1$ до $n$ включительно такое, что в разложении его на простые множители количество множителей максимально. Если таких чисел несколько, выбрать максимальное из них.

Например, если $n = 7$, то ответом будет число $6$, как наибольшее число, имеющее в своем разложении $2$ простых множителя $2$ и $3$.

Входные данные

Одно целое число $n$ $(1 ≤ n ≤ 2$³¹$- 1)$.

Выходные данные

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

Тесты

Ввод Вывод
1 1 1
2 10 8
3 100 96
4 363 256
5 2147483647 1610612736

Код программы

Решение

Для решения данной задачи нам необходимо понять, что чем меньше простой множитель, тем больше таких множителей может содержать в себе искомое число, значит наше число состоит только из двоек или из двоек и одной тройки.

Создадим две переменные равные двум и трём и будем увеличивать их вдвое до тех пор, пока полученное число не превосходит заданное.

Из полученных двух чисел выберем наибольшее, как этого требует условие задачи.

Заметим, что если заданное число будет единицей, двойкой или тройкой, то его и надо вывести на экран.

Ссылки

Задача множители на e-olymp

Решение задачи на Ideone

e-olymp 421. Йо-йо

Задача

Игрушка йо-йо состоит из катушки, на которую намотана нитка. Если, держа за конец нитки, отпустить катушку, то она будет, вращаясь, сначала опускаться вниз, а затем по инерции подниматься вверх. Но высота, на которую катушка поднимется, будет в $k$ раз меньше, чем высота, с которой она опустилась. Будем считать, что катушка остановилась, если высота её очередного подъема не превышает $1$.

Напишите программу, которая по длине нитки $l$ и коэффициенту $k$ считает количество подъемов катушки до остановки. Например, пусть $l = 17$ и $k = 2$, тогда катушка будет подниматься на высоты $8.5$, $4.25$, $2.1254$, $1.0625$, а затем остановится. Таким образом получится $4$ подъема.

Входные данные

Два целых числа $l (1 ≤ l ≤$ 109$)$ и $k (2 ≤ k ≤ 100)$.

Выходные данные

Вывести одно число – количество подъемов.

Тесты

Ввод Вывод
1 17 2 4
2 4 2 1
3 135 9 2
4 1 2 0
5 1000000000 100 4

Код программы

Решение

Для решения данной задачи достаточно найти максимальную степень $k$, которая будет меньше числа $l$. Значение показателя степени и будет количеством подъемов йо-йо. Ответ найдем с помощью логарифма, подключив библиотеку <cmath>. Используем формулу перехода логарифма к новому основанию, а каким будет это основание значения не имеет. Заметим, что нас интересует только целая часть логарифма — число подъемов.

Также необходимо учесть, что кaтушка остановится в случае, если высота её очередного подъема будет меньше либо равна $1$. Это означает, что, если $l$ будет степенью $k$, полученный с помощью логарифма ответ будет на единицу больше верного. Введем очень маленькую константу с для разрешения этой проблемы. На ответ она особо не повлияет, а вот от единицы поможет избавиться.

Ссылки

Решение задачи на Ideone

Задача 421 на e-olymp