Как решить алицею на спой. Как у него есть общий образец для его ответа
Какова логика, лежащая в основе паттерна, т.е.(ans=(n+1)/2) в вопросе ALICESIE о спой.
Algorithm_given:
1.Создайте список последовательных целых чисел от N до 2 (N, N-1, N-2, ..., 3, 2). Все эти номера N-1 изначально не отмечены.
2. Вначале пусть P будет равно N, и оставьте это число без отметки.
3. Отметьте все правильные делители P (т. Е. P остается без опознавательных знаков).
4. Найдите наибольшее неотмеченное число от 2 до P - 1, и теперь пусть P равно этому числу.
5. Если в списке больше не было номеров без опознавательных знаков, остановитесь. В противном случае повторите с шага 3.
Найти общее количество номеров без опознавательных знаков.
я знаю его решение O(sqrt(n)), но ответ ожидается в O(1), его можно найти, увидев общий шаблон т.е.(N+1)/2
Но как это доказать математически
ссылка: ALICESIE