Проблема с 2-х клавишной клавиатурой

Для данного положительного целого числа N и строки S , изначально равной «A» , задача состоит в том, чтобы минимизировать количество операций, необходимых для формирования строки, состоящей из N чисел A, путем выполнения одной из следующих операций на каждом шаге:

• Скопируйте все символы, присутствующие в строке S.
• Добавьте к строке S все символы, которые были скопированы в последний раз.

Примеры:

Input: N = 3
Output: 3
Explanation:
Below are the operations performed:
Operation 1: Copy the initial string S once i.e., “A”.
Operation 2: Appending the copied string i.e., “A”, to the string S modifies the string S to “AA”.
Operation 3: Appending the copied string i.e., “A”, to the string S modifies the string S to “AAA”.
Therefore, the minimum number of operations required to get 3 A’s is 3.

Input: N = 7
Output: 7

Подход: Данная проблема может быть решена на основе следующих наблюдений:

1. Если N = P ₁ *P ₂ *P _m , где {P ₁ , P ₂ , …, P _m } — простые числа, то можно выполнить следующие ходы:
   1. Сначала скопируйте строку, а затем вставьте ее (P ₁ – 1) раз.
   2. Точно так же снова копируем строку и вставляем ее (P ₂ – 1) раз.
   3. Выполнив M раз с оставшимся простым числом, можно получить строку с N количеством букв A.
2. Таким образом, общее количество необходимых минимальных ходов определяется выражением (P ₁ + P ₂ + … + P _m ) .

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем , как 0 , которая хранит результирующее количество операций.
• Найдите простые множители и их степени данного целого числа N.
• Теперь переберите все простые множители N и увеличьте значение ans на произведение простого множителя и его степени.
• Наконец, после выполнения вышеуказанных шагов выведите значение ans как результирующее минимальное количество ходов.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(√N)
Вспомогательное пространство: O(1)