Two Measurements
Time limit2sMemory limit512 MB
Count pairs of hours i < j in [l, r] whose difference is a multiple of the rotation period a.
- Level
Medium4 of 10
- Topics
- Math, Combinatorics, Implementation
- Solved
- No attempts yet
Problem
Scientists plan to run an important experiment using a research module on the planet X-2019. The experiment involves two measurements: a main one and a control one. Each measurement takes exactly one hour and must begin a whole number of hours after the research module starts operating.
The experimental data is to be sent to an orbital station immediately. The communication channel with the orbital station is open from hour l to hour r after the research module starts operating, inclusive. In addition, the experiment plan requires the planet to complete a whole number of rotations about its axis between the measurements. The planet X-2019 completes one rotation about its axis in a hours.
Thus, if the measurements are taken during hour i and hour j, then l ⩽ i < j ⩽ r must hold, and (j − i) must be a multiple of a. The scientists now need to determine how many distinct ways there are to take the measurements.
Write a program that, given the measurement time bounds l and r and the planet's rotation period a, determines the number of possible ways to take the measurements: the number of pairs of integers i and j such that l ⩽ i < j ⩽ r and (j − i) is a multiple of a.
Input
The input contains three integers, one per line: l, r, and a (1 ⩽ l < r ⩽ 10^9, 1 ⩽ a ⩽ 10^9).
Output
Print a single integer: the number of ways to take the measurements.
Hint
In the first example, the measurements can be taken during the following pairs of hours: (1, 3), (1, 5), (2, 4), (3, 5).
In the second example, the communication channel is not open long enough to take two measurements.