I failed this problem at a contest !

[ne555]

More 5's than 2's
By instance considerer the range [125, 126] There are three 5's and only one 2
125*126 = 15750 <--- one trailing zero

What about number_of_factors()?

That's left as an exercise to the reader. ;)
Suppose that you factorise 20! How many 5's will show up? (when do they show up?)
Now try it with 25! and 169!

@m4ster r0shi: time limit exceeded.

30% of the tests done to the .cpp file will have b-a <= 100000

So input like 1 2000000000 is allowed.

[m4ster r0shi]

ne555 wrote:

time limit exceeded

Crap...

ne555 wrote:

That's left as an exercise to the reader

Ok, tell me if I'm getting close...

10! = 1*2*3*4*5*6*7*8*9*10.
number_of_factors(10!) = 2 = 10/5.

20! = 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20.
number_of_factors(20!) = 4 = 20/5.

25! = ...
number_of_factors(25!) = 6 = 25/25 + 25/5.

50! = ...
number_of_factors(50!) = 12 = 50/25 + 50/5.

1000! = ...
number_of_factors(1000!) = 249 = 1000/625 + 1000/125 + 1000/25 + 1000/5.

I believe helios is doing something similar here, but I can't
really tell what exactly he's doing, as his code is too compact.

for (unsigned i=1;i<=13;i++,power*=5){
    zeroes+=c/power;
    unsigned mod=c%power;
    if (mod && (!(a%power) || a%power>=power-mod+1))
        zeroes++;
}

[hamsterman]

#include <iostream>

inline int count_multiples(int a, int b, int n){
    if( a%n != 0 ) a += n - a%n; 
    return ( b - a + n )/n;
}

inline int count(int a, int b, int n, int log_n_of_2_to_31){
    int c = 0;
    for(int i = 0, p = n; p <= b && i < log_n_of_2_to_31; p*=n, i++)
        c += count_multiples(a, b, p);
    return c;
}

inline int min(int a, int b){ return a > b ? b : a; }

int main(){
    int a, b;
    std::cin >> a >> b;
    std::cout << min( count(a, b, 2, 30), count(a, b, 5, 13) );
    std::cin.ignore().get();
    return 0;
}

Pretty much what helios did, just cleaner (and with 2s). Though I didn't test it much..

[ne555]

int number_of_factors( int n, int fact ){
	int total=0;
	while(n){
		n /= fact;
		total += n;
	}	
	return total;
}

Avoid the danger of overflow. (and magic numbers)

    unsigned mod=c%power;
    if (mod && (!(a%power) || a%power>=power-mod+1))
        zeroes++;

What is happening here a%power>=power-mod+1 ?

[helios]

It does a lot of magic with modulo. My reasoning is as follows:
A=[a;b]
c=#A
If c is a multiple of 5, there is always the same number of multiples of 5 in A (c/5).
Otherwise, it depends on c%5 and a%5.

c%5==1:
(The sets are modulo 5 to make my point easier to see.)
a%5==0: {0,1,2,3,4,0} *
a%5==1: {1,2,3,4,0,1}
a%5==2: {2,3,4,0,1,2}
a%5==3: {3,4,0,1,2,3}
a%5==4: {4,0,1,2,3,4}
There's c/5+1 zeroes when a%5==0.

c%5==2:
a%5==0: {0,1,2,3,4,0,1} *
a%5==1: {1,2,3,4,0,1,2}
a%5==2: {2,3,4,0,1,2,3}
a%5==3: {3,4,0,1,2,3,4}
a%5==4: {4,0,1,2,3,4,0} *
There's c/5+1 zeroes when a%5 in {0,4}.

c%5==3:
a%5==0: {0,1,2,3,4,0,1,2} *
a%5==1: {1,2,3,4,0,1,2,3}
a%5==2: {2,3,4,0,1,2,3,4}
a%5==3: {3,4,0,1,2,3,4,0} *
a%5==4: {4,0,1,2,3,4,0,1} *
There's c/5+1 zeroes when a%5 in {0,3,4}.

c%5==4:
a%5==0: {0,1,2,3,4,0,1,2,3} *
a%5==1: {1,2,3,4,0,1,2,3,4}
a%5==2: {2,3,4,0,1,2,3,4,0} *
a%5==3: {3,4,0,1,2,3,4,0,1} *
a%5==4: {4,0,1,2,3,4,0,1,2} *
There's c/5+1 zeroes when a%5 in {0,2,3,4}.

Notice that if we extend the sets again, they will all have one more zero, since c%5==0 in that case.

We see that:
1. If a%5==0, there's always an extra zero.
2. The second half of the set begins at a number that depends on c%5. Specifically, {0}∪[6-c%5;4]

Et cetera for extending to an arbitrary power of 5.

EDIT: I'm not exactly sure what you people are doing. What the above does is count how many pental numbers in A end in some number of zeroes.
EDIT 2: Oh... I see, now.
EDIT 3: Fixed [125;126] bug:

unsigned count_round_numbers(unsigned a,unsigned b,unsigned base,unsigned max_power){
	unsigned zeroes=0,
		power=base,
		c=b-a+1;
	for (unsigned i=1;i<=max_power;i++,power*=base){
		zeroes+=c/power;
		unsigned mod_c=c%power,
			mod_a=a%power;
		if (mod_c && (!mod_a || mod_a>=power-mod_c+1))
			zeroes++;
	}
	return zeroes;
}

unsigned count_trailing_zeroes_in_fact_b_div_fact_a(unsigned a,unsigned b){
	unsigned zeroes=0;
	if (a==b){
		unsigned temp=a;
		while (!(temp%10)){
			zeroes++;
			temp/=10;
		}
	}else
	//2,000,000,000 == 1304400000000 (13 digits) in pental
	//2,000,000,000 == 1110111001101011001010000000000 (31 digits) in binary
		zeroes=std::min(count_round_numbers(a,b,2,31),count_round_numbers(a,b,5,13));
	return zeroes;
}

[hamsterman]

I just realized something. ( b - b%n - a + n )/n; is all you need to know how many multiples of n there are in range [a;b]