Какова логика, лежащая в основе шаблона, то есть (ans = (n + 1) / 2) в вопросе ALICESIE на spoj.
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