Find a sequence of integer powers faster than the naive algorithm
In the worst case, this seems to be optimal. If your $a_i$ are pairwise coprime,
e.g. $k$ different primes, they powers do not share any factors.

Of course, if $k$ is large but $c$ from your proposed restriction is small, there 
may not be such a set; then, you powers share factors. You could exploit this
if you knew the shared factors for your $a_i$; but finding those is harder than
just computing all the powers.

So I daresay, no, you can not do this faster without more knowledge about the $a_i$.