10212 - The Last Non-zero Digit.

[colinhunt83]

A simple iterative multiplicative approach can get AC here taking ~4.5 seconds. No prime factorization needed, other than recognizing the trick with 2s and 5s.
However, if your approach is O(c*f(n)), c matters here. Example: if my solution was tripled then it would get TLE. (hint: only use one loop)

[bati06]

Hi!

I just want to point out that there are some modulo arithmetic solutions posted on the internet (1, 2, 3, ...) which get AC on UVa OJ but they are not correct.

It is not enough to keep remainder by 1e9.
See input "9765634 10" and "9765625 10". Correct output is "2" and "3" respectively.

This is because multipling by 9765625 (= 5^10) is generating a lot of 0 digit (ten, to be exact) at the end of the result. So we should keep remainder by 1e11 for not loosing information. (If you iterating from lower number to upper than 1e10 is enough.)

Any feedback is wellcome.

[catweazle352]

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

[abu_raihan]

Why this is getting WA?? can anyone help??

while (scanf("%lld %lld", &n, &m) == 2)
{
LL s = n-m+1;
LL ans = 1, i;

for(i=s; i<=n; i++)
{
ans *= i;
while(!(ans%10))
ans /= 10;
ans %= 10000000000;
}

printf("%lld\n", ans%10);
}