Sum of an Arithmetic Sequence

Time limit2sMemory limit128 MB

Summary

Given l, r and k (2 to 5), count integers in [l, r] that can be written as the sum of the first k terms of an arithmetic sequence with positive first term and positive common difference.

Level: Medium5 of 10
Topics: Math, Number theory, Implementation
Solved: No attempts yet

Problem

The first k terms of an arithmetic sequence whose first term is x and common difference is d are as follows.

x, x + d, x + 2d, ..., x + (k - 1)d

Here, both x and d are positive integers. Say that a number can be represented if it is the sum of the first k terms of such an arithmetic sequence. Count how many integers from l to r, inclusive, can be represented in this way.

Input

The positive integers l, r, and k are given in this order, one per line.

1 <= l <= r <= 1,000,000,000

2 <= k <= 5

Output

Print the number of integers satisfying the condition.

Hint

6 = 1 + 2 + 3, 9 = 2 + 3 + 4 = 1 + 3 + 5, and 12 = 3 + 4 + 5 = 2 + 4 + 6 = 1 + 4 + 7.

Examples5

Example 1
Input
```
1
12
3
```
Expected output
```
3
```
Example 2
Input
```
1
10
2
```
Expected output
```
8
```
Example 3
Input
```
20
30
4
```
Expected output
```
6
```
Example 4
Input
```
1
9
4
```
Expected output
```
0
```
Example 5
Input
```
1
13
4
```
Expected output
```
1
```