Nevertheless there is an O(log_10(n)) solution.

Pre-Calculate all blocks with 18 numbers with suffixes 21..39 and 61..79. e.g. 121*122*..*129*131*132*..*139 (same with 61..79) and store results in an array [2][400000].

Note that even 5^10 will be compensated this way if you do the precalculation correctly.

Next, observe that each block with suffixes 01...19, 41..59 and 81..99 will always give the *same* result (2, 6 and 2 respectively). E.g. 5241*5242*5243*...*5249*5251*...*5259 will result in 2 as will the block 68478341*...*68478359.

The number of such blocks in a range can easily be calculated. And then if you have for example k blocks of type e.g. 81...99, observe that the results of multiplying these k blocks with themselves, you get 2^k and the result of 2^k will cycle the sequence 2,4,8,6,2,4,8,6,2,.... Doing some easy modulo-calculation k mod 4 now gives you a direct solution.

Lastly don't worry about numbers with a trailing zero. Just treat them like normal numbers, i.e. reduce them:

e.g. 82399*...*3121 will result in:

calculate 80000*70000*60000*...*10000 = 8*7*6*5*4*3*2*1, calc directly, these are max 10 multiplicatioms

82000*81000*...*4000 = 82*81*...*4 use block algorithm mentioned above, because of precalc and the modulo-tricky described above this will be done in constant time.

82300*82200*...*3200 = 823*822*...*32 again use block algorithm mentioned above

82390*82380*...*3130 = 8239*..*313 again use block algorithm mentioned above

Of course, because not always the ranges will start and end at block boundaries, you will have do do at most 18 manual calculations at each power-of-10-level in order to clip calculation ranges to block boundaries.

Conclusion:

There is a constant number of calculations at each power-of-10-level. Therefore, it all sums up to time complexity O(log_10(n)).

I implemented this algorithm an got accepted in 0,180 sec although I used java for implementation.

Of course, the O(n) solution is much much much easier to implement. To be honest: I didn't see that simple linear solution because I thought I have to do it in logarithmic time due to high boundaries.

Christof