Clown, не пытайтесь придумать алгоритм для этой задачи. Всё что вам нужно - это найти зависимости между переменными и составить уравнение. К сожалению я сейчас не могу помочь вам с решением, возможно в один из ближайших дней на следующей неделе. Я более чем уверен, что для любого вашего алгоритма найдется такое N, которое провалит тест по времени выполнения. Начните с определения того, что Фернандо считает звездой.
Составьте примерный вход - выход для идеально правильной программы, хотя бы для первых нескольких значений. Найдите принцип, по которому изменяется выходное значение, слепите формулу, и задача решена самым оптимальным образом.
Upd:
В промежутке 1 < k < N/2 вам нужно найти числа, которые не являются делителями N, узнать их кол-во, и прибавить 1. Это и будет ответом.
Пример:
Делители числа N=8 попадающие в заданный промежуток это 1, 2, 4, 8. т.е. делителями не являются 3, 5, 6, 7. в промежуток попадает только число k=3, прибавляем единицу (т.к. 1 - это делитель любого числа, и для него звезда всегда будет строиться)
получаем выходной ответ: 2
Делители числа N=9 это 1, 3, 9. делителями не являются 2, 4, 5, 6, 7, 8. В промежуток(1 < k < N/2) попадают 2 и 4. прибавляем к кол-ву этих чисел 1, получаем ответ:3
Делители числа N=10 это 1, 2, 5, 10. не делят 3, 4, 6, 7, 8, в промежуток попадают 3 и 4, кол-во = 2, прибавляем 1, ответ:3
итд...
Промежуток 1 < k < N/2 снизу ограничивает 1, из которого звезда получится в любом случае. сверху ограничивает максимально разумный диапазон (дальше звезды начнут повторяться, только в другую сторону, например для N = 9 звезды будут при k1=3, k2=4, k3=5=(9-4), звезда аналогичная той, что будет при k2=4, и k4=6=(9-3) - звезда аналогичная звезде при k1.
http://codeforces.ru/blog/entry/651?locale=ru