Counting Multiples
Autumn Tournament (2007)
Submission name: div.cpp
Problem summary
Count the integers in the inclusive interval [a,b] that are divisible by c.
Input
Three integers a, b and c.
Output
The number of multiples of c in the interval.
Constraints
0 < a < b < 10^15; 1 < c < 10^15.
Worked example
Original statement sample.
Input
7 60 15
Output
4
Solution analysis
- The positive multiples of c are c, 2c, 3c, and so on. Exactly floor(x/c) of them are at most x.
- Subtract the number at most a−1 from the number at most b. Using a−1, rather than a, keeps a itself when it is divisible by c. Integer division performs the floor because all values are nonnegative.
- For [7,60] with c=15, floor(60/15)=4 and floor(6/15)=0. The four values are 15, 30, 45, and 60.
Why it works
The multiples at most b split disjointly into those below a and those in [a,b]. Removing the first group leaves exactly the requested group.
Complexity: O(1) time and O(1) extra space; the computation uses two divisions.
Watch out. Do not loop over an interval that may contain almost 10^15 values. Use long long; int cannot store the bounds.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int main(){
long long a,b,divisor;
cin>>a>>b>>divisor;
// Prefix counts preserve both inclusive endpoints.
cout<<b/divisor-(a-1)/divisor<<'\n';
}