Benny and GCD

4

7 votes
Mathematics, Approved, Easy, Greatest common divisor
Problem

Probably, you have already guessed that Benny doesn't like math at all. Especially, she is really bad at number theory.

Little Benny wants you to answer one single questions that disturbs her every night.

You will be given three integers: l, r, g. You have to output the number of pairs of integers x and y such that gcd(x,y)=g and lx,yr.

Note that pairs (1,2) and (2,1) are different.

Input format

The first line contains three integers l, r and g

Constraints

1l,r,g109

0rl103g

Output format

Output single integer: the answer to the problem.

Sample Input
1 11 5
Sample Output
3
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

The following pairs formed the answer: (5,5), (5,10), (10,5). As you can see there are only three such pairs.

Editor Image

?