Автоморфы

Помогите решить олимпиадную задачу.
Дано число 0<n<100. Найти все n-значные числа-автоморфы.
Автоморф - число, которое при возведении в квадрат на конце дает само себя.
Ограничение по времени: 0.5с.
Пример входных данных: 4
Пример выходных данных: 9376

Что я делал. Во-первых, вывел, что a n-значный автоморф <=> a*(a-1) делится на 10^n.
Попытался запрограммировать следующим образом:
Смотрим 1-е числа: 1^2=...1, 5^2=...5, 6^2=...6.
2-е: двузначное автоморф только если в числе единиц автоморф; перебираем...
И т.п.
Естественно, для 100-значного числа тупое перемножение не прокатит. Что делать?
Символьная арифметика? За 0.5с не уложиться...