My solution (without answers precalculation) is about O(N^2). How could it be solved faster?

I wonder the solution within O(n^2) without cheating.

Yes there is. You must solve this mathematically.
Solution:
Let find all numbers of length 2.Let a is automorphic number then a * (a - 1) = 0(mod 100). Then we know that a and (a - 1) is coprime this fact gives us two cases :
1)a is multiple of 25=> a = 25 * q  and (a - 1) is multiple of 4 => a - 1 = 4 * p =>
25q - 1=0(mod 4) => 25q = 1(mod 4)
then we must find such v s.t. 25 * v = 1 (mod 4), but we know that 4 and 25 coprime => such v exists moreover we can find it use extended Euclid algorithm. In this case v = 1 because 25 * 1 = 1 (mod 4). Then we have (25 * v) * q = 1 * v(mod 4)=>  q = 1(mod 4) => q = 1 then
a = 25 * q => a = 25-is automorphic number.
2)(a - 1) is multiple of 25 and a is multiple of 4. a = 25q + 1 then use idea described above we find that q = 3 => 25 * 3 + 1=76- is automorphic

Using this idea we can find all automorphic numbers which length is <= then given n !