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)
10212  The Last Nonzero Digit.
Moderator: Board moderators

 New poster
 Posts: 1
 Joined: Fri Jan 30, 2015 2:01 am
Re: 10212  The Last Nonzero Digit.
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.
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.

 New poster
 Posts: 10
 Joined: Wed Aug 14, 2013 7:53 pm
Re: 10212  The Last Nonzero Digit.
Nevertheless there is an O(log_10(n)) solution.
PreCalculate 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 modulocalculation 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 modulotricky 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 powerof10level in order to clip calculation ranges to block boundaries.
Conclusion:
There is a constant number of calculations at each powerof10level. 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
PreCalculate 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 modulocalculation 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 modulotricky 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 powerof10level in order to clip calculation ranges to block boundaries.
Conclusion:
There is a constant number of calculations at each powerof10level. 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
It's easy to beef about something  but it's much harder to make it better

 New poster
 Posts: 1
 Joined: Mon Nov 20, 2017 10:58 am
Re: 10212  The Last Nonzero Digit.
Why this is getting WA?? can anyone help??
while (scanf("%lld %lld", &n, &m) == 2)
{
LL s = nm+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);
}
while (scanf("%lld %lld", &n, &m) == 2)
{
LL s = nm+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);
}