Всем доброго дня!

Дочка принесла из универа задачку с очень простой формулировкой, но уже пару недель не получается сдать (проверяет стандартная система автопроверки). Сейчас сдача уже не актуальна, на зачет баллов набрала, но вопрос, как же надо было решать, по прежнему свербит. Поэтому, если кто-то ткнет носом в правильный вариант, буду весьма признателен.

Задачка такая: дано простое число p<10^9, положительное целое число a<p и диапазон чисел [l;r], 0<=l<=r<p. Требуется вывести в порядке возрастания все числа из диапазона, которые представимы в виде a^k mod p для какого либо k. Гарантируется, что таких чисел (которые составляют ответ) не более 100 штук.
Ограничения по памяти 256Mb, ограничение по времени 3.5 сек.
Все варианты, которые пробовали, рано или поздно вылетают по TimeLimit'у.

Пробовали следующие варианты:
1. Наивный подход: последовательно вычисляем все степени числа a по модулю p, запихивая результаты в std::set или взводя элементы в vector<bool>, как только нашли элемент, который уже встречался, выходим, т.к. дальше пойдет повторение. Этот вариант не проходит тест раньше всех.
2. Модификация первого подхода: посчитать, какая степень а разделяет (r+1) и (p+l), по выходу из диапазона [l,r] сразу домножать на эту степень, а не постепенно, много раз на a. Проходит всего на 1 тест больше.
3. Перебор всех чисел от l до r и проверка того, может ли это число быть степенью a по модулю p. Проверяли с помощью алгоритма поиска (дискретного логарифма в кольце вычетов по простому модулю).

Комбинация 2 и 3 (в зависимости от величины (r-l)) проходит на 4 теста больше, чем наивный подход, но все равно валится по TimeLimit'у.

Варианты 1 и 2 не годятся, если a — первообразный корень по модулю достаточно большого p (просто цикл получается чересчур длинным), вариант 3 — слишком "тяжелый" для больших диапазонов [l;r].
Вероятно, надо как-то использовать информацию о том, что в ответе не более 100 чисел, но такое возможно в обоих перечисленных раскладах (длинный цикл, но узкий диапазон [l;r], либо наоборот, диапазон широкий, но цикл короткий).

Есть подозрение, что использованный алгоритм поиска дискретного логарифма для проверки представимости числа степенью по модулю это слишком сложный инструмент для простой задачи, и есть что-то более эффективное. Или есть в принципе какой-то простой подход, который почему-то не приходит в голову.

В общем, буду благодарен за любые подсказки.

P.S. Задача для первокурсников, серьезных знаний по теории чисел не предполагается (даже тех, о которых я упомянул).
P.P.S. Задачка появилась в контесте на стандартные структуры данных (т.е. те, которые доступны в библиотеках типа STL для C++) — возможно, это как раз и есть главная подсказка, но мы ее не поняли.