$625 \times 16 = 10000$
i.e. anything which is multiple of 10000 will also be multiple of 625
$\underbrace{8888 \cdots 8}_{\text{100 times}} =\underbrace{8888 \cdots 8}_{\text{96 times}} \times 10000 +8888$
So to find reminder of $\underbrace{88888888888888\cdots 8}_{\text{100 times}}$, just find Reminder when 8888 is divided by 625
$8888 = 625 \times 14 + 138$
So, 138 is reminder.