Trailing Zeros of Selected Factors
National Olympiad — National round (2019 season)
Submission name: product.cpp
Problem summary
Multiply all integers x in the inclusive interval [a,b] that are divisible by d. Find the number of trailing decimal zeros in the product, without constructing the product.
Input
Three positive integers d, a, b.
Output
The number of trailing zeros.
Constraints
0 < a < b < 10000000000; (b−a)/10000000 < d ≤ b−a+1; memory limit 2 MB.
Worked example
An independently prepared example for this explanation.
Input
5 4 20
Output
3
Solution analysis
- A trailing zero requires one factor 2 and one factor 5. Thus the answer is the smaller of the product’s total exponents of 2 and 5.
- Write each selected value as d·k, where first=ceil(a/d) and last=floor(b/d). The product is d^count multiplied by first·(first+1)·…·last. For p=2 and p=5, its exponent is count·vp(d)+vp(last!)−vp((first−1)!).
- Compute vp(t!) as floor(t/p)+floor(t/p²)+… by repeatedly dividing t by p. In the sample, selected factors are 5,10,15,20. They contain three factors 2 and four factors 5, so the product has min(3,4)=3 trailing zeros.
Why it works
Factoring every selected multiple into d times its index proves the product decomposition. For any prime p, each multiple of p contributes one p, each multiple of p² contributes another, and so on, yielding the factorial exponent formula. Unique prime factorization then makes the number of complete factors 10 exactly min(v2,v5).
Watch out. Do not count only the selected numbers divisible by 10: separate factors can combine into tens. Repeated powers such as 20 contribute more than one factor 2.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
long long factorialExponent(long long n, int prime) {
long long exponent = 0;
while (n > 0) {
n /= prime;
exponent += n;
}
return exponent;
}
long long productExponent(long long d, long long first, long long last, int prime) {
long long inD = 0;
long long value = d;
while (value % prime == 0) {
++inD;
value /= prime;
}
long long count = last - first + 1;
// Selected multiples are d^count times a consecutive product of indices.
return count * inD + factorialExponent(last, prime) - factorialExponent(first - 1, prime);
}
int main() {
long long d, a, b;
cin >> d >> a >> b;
long long first = (a + d - 1) / d;
long long last = b / d;
if (first > last) {
cout << 0 << '\n';
return 0;
}
long long twos = productExponent(d, first, last, 2);
long long fives = productExponent(d, first, last, 5);
cout << min(twos, fives) << '\n';
}