Trailing Zeros in an Interval Product
National Olympiad — Municipal round (2024 season)
Submission name: product.cpp
Problem summary
Find the trailing-zero count of a(a+1)…b without constructing the enormous product.
Input
a b.
Output
The trailing-zero count.
Constraints
1≤a<b≤10000000.
Worked example
Input and output for the worked example discussed below.
Input
50 53
Output
2
Solution analysis
- Each factor 10 needs one factor 2 and one factor 5. The answer is the smaller of their total exponents; an arbitrary interval requires calculating both.
- Write the interval product as b!/(a−1)!. For prime p, its exponent in x! is floor(x/p)+floor(x/p²)+… . Repeated division sums these layers without storing powers. Subtract the exponent of the lower factorial.
- For 50…53, the product has two factors 5 from 50 and three factors 2 from 50 and 52. Thus min(2,3)=2, matching 7027800.
Why it works
Multiples of p contribute the first p factor, multiples of p² another, and so forth, counting every factor exactly. Factorial subtraction isolates [a,b]. Pairing twos with fives gives exactly the factors 10.
Complexity: O(log b) time and O(1) auxiliary space.
Watch out. Use a−1, count repeated factors, and never build the product.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
using namespace std;
long long exponent(long long number,int prime){
long long total=0;
while(number>0){
number/=prime;
total+=number;
}
return total;
}
int main(){
long long a;
long long b;
cin>>a>>b;
// Factorial differences isolate the interval's prime exponents.
long long twos=exponent(b,2)-exponent(a-1,2);
long long fives=exponent(b,5)-exponent(a-1,5);
cout<<min(twos,fives)<<'\n';
}