OJ Board

Can anyone tell me how to solve this problem?

I have a problem with the complexity of my algorithm to solve this problem.

let pick N and M, with N >= M
if we do:

[cpp]
unsigned long i, k = 1;
for(i=M+1;i<=N;i++) {
k = k * i;
takeTheZerosFrom(k);
takeTheGoodPartOf(k);
} printf("%u\n",lastDigitOf(k));
[/cpp]

it produces the right solution.
takeTheZerosFrom's functionality the name tells
takeTheGoodPartOf take the k and let k with the last 7 numbers of k

ex: k = 2355356200
after doing takeTheZerosFrom we have
k = 23553562
after doing takeTheGoodPartOf(k) we have
k = 3223562

The problem with this algorithm is that the complexity is O(N)
and it is sure that it's a TLS...
How can we improve this complexity??

Thanks in advance,

Pedro Machado


I tried to solve this problem with the basic idea of taking the k - las digits of the

Let l = length of N = O(log(N))
The complexity of this your algorithm is O(N) = O(10^l).

U have to solve it like 568
first take a array from the 1st input to 2nd input
then find the co-factors of the primes of every number
of the 1st and second input then multiply them and find
mod of ten and remember to reduce the no. of co-factors
of 5 from the co-factors of 2.

I try very hard to figure out what you said in the previous post.
I got some idea from that, but I am not very sure what I think is the same as you. Thanks any way, I got AC in 9.10 seconds. Now my question is that somebody solve this 10212 so quickly (less than 1 second). How to do?

[size=24][/size]
I don't know how to solve this problem without time limit.

My algorithm is :
last = 1;

1. for (k=n-m+1; k<=n; k++)
----- find the count of factor 2 and factor 5;
2. for (k=n-m+1; k<=n; k++) {
------ while (!(k%5) && count_5>0) { k/=5; count_5--; }
------ while (!(k%2) && count_2>0) (k/=2; count_2--; }
-------last = multiply (k, last);
-------last = last digit of variable 'last';
}
3. print last;

for n<=1000000 && m<= 1000000 my code run fast enough,
but for n = 20000000 and m = 20000000 my code stuck here.

if anyone have time, please help me .

Thanks. [/code]

You know your algorithm is much like mine, but I managed to get AC in 9.650 sec.

Try to optimize your code a bit - do everything in one loop.

P.S. The problem can be solved faster, but when I coded it I was lazy enough and I didn't want to optimize it although I was almost the last in the ranklist.

Good luck!

What do tou mean by :
--"Do Everything in one loop ?"

How can I know the number that must be divided by two or by five, if I count the factor of two and five in one loop ?

Please Help me ....
Thanks.

First you count last without factors 2 and 5. Then after the main loop you start loop from 1 to count2-count5 and multiply last by 2 in it. That's enough. And only one BIG loop.

Try it and get AC.

I use following algorithm and got WA in less then 1 sec .... Could anyone tell me why ?

we could calculate value of expression N!/(N-M)! (isn't it ? )
1. factorize N! - when it's done, I got N! in form 2^a*3^b.....
2. factorize (N-M)! - I got the same form ....
3. substract powers: from powers of (1) substract powers of (2)
4. substract power of 2 with power of 5 ....
5. calculate last digit, knowing that powers of 2 are ending with 1,2,4,8,6,2,4 ... and so on for 3,7,9and 1 ....
6. print last digit ....

Could anyone help me ?
Regards
Dominik

Too little information. Give me your implementation if step 5 - I'll try to think it over and help if I find some bug.

When I come back to home from work, I send you my implementation of this problem ... maybe I made something wrong

Regadrs
Dominik

Dominik, I found a bug in your code. You use primes till sqrt(20000000), but that's wrong. Your algorithm requires primes till 20000000 as N! can contain prime factors up to N. For example your program for N=7777 and M=234 gives answer 4 but the correct answer is 2.

Anyway your algorithm is quite interesting. It would be even fantastic if sqrt(N) were enough...

Good luck!

When I wiat for your answer, I modify my code i this way, that I calculate all primes not to 5000, but to 20000000 (max N in problem) ... My program run about 5,4 sec , but still WA ... I check your input as soon as possible ... maybe I found another bug ....

But thank you very much for your help )

Dominik

Well, I have try to solve this Problem for a month, but I still got Time Limit.
I have change my algo (first I count last without factor 2 and factor 5),
and after that i start loop from n-m+1 to n(inclusive) and multiply last by 2 or 5.

As in:

count2= 0; count5=0; last=1;
for (i=n-m+1; i<=n; i++) {
-- tp = i;
-- while (!(tp%10)) tp/=10;
-- while (!(tp%2)) {
------ tp/=2;
------ count2++;
-- }
-- while (!(tp%5)) {
------ tp/=5;
------ count5++;
-- }

--tp = lastdigit(tp);
--last *= tp;
--last = lastdigit(last);
}

if (count2 >= count5) {
---- for (i=count5+1; i<=count2; i++) {
--------last *=2;
---------last = lastdigit(last);
------}
}
else {
---- for (i=count2+1; i<=count5; i++) {
---------last*=5;
---------lastdigit(last);
-----}
}

printf ("%d\n", last);
------------------------------------------------------
Please Help me ...
Thanks.