All Tracks Math Number Theory Problem

Benny and GCD
Tag(s):

Easy, Easy, Math

Problem
Editorial
Analytics

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 $$l \leq x, y \leq r$$.

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

Input format

The first line contains three integers $$l$$, $$r$$ and $$g$$

Constraints

$$1 \leq l, r, g \leq 10^9$$

$$0 \leq r-l \leq 10^3 \cdot g$$

Output format

Output single integer: the answer to the problem.

SAMPLE INPUT
1 11 5
SAMPLE OUTPUT
3
Explanation

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

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

January Clash '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications