All Tracks Math Number Theory Totient Function Problem

Monk And ETF
Tag(s):

Euler's totient function, Mathematics, Medium-Hard, Sieve

Problem
Editorial
Analytics

Link to Russian translation of problem

Monk has been solving a lot of mathematical problems recently. He was learning ETF (Euler Totient Function) and found the topic quite interesting. So, he tried solving a question on ETF. He will be given two numbers L and R. He has to find the probability that the ETF of a number in the range [L, R] is divisible by a number K.
Note:
ETF is an arithmetic function that counts the positive integers less than or equal to N that are relatively prime to N. To learn more about ETF, click here.

Input:
The first line contains the number of test cases i.e. T.
The next T lines will contain three integers L, R and K.

Output:
Print the answer in a new line after rounding off the first 6 digits after the decimal place.

Constraints:
1 <= T <= 10
1 <= L <= R <= 1012
0 <= R - L <= 105
1 <= K <= 106

SAMPLE INPUT
3
1 4 2
2 5 2
3 10 4
SAMPLE OUTPUT
0.500000
0.750000
0.375000
Explanation

In Case 1:
ETF values of numbers from 1 to 4 are - 1, 1, 2, 2. Probability that ETF value is divisible by 2 is (2/4) = 0.5
In Case 2:
ETF values of numbers from 2 to 5 are - 1, 2, 2, 4. Probability that ETF value is divisible by 2 is (3/4) = 0.75
In Case 3:
ETF values of numbers from 3 to 10 are - 2, 2, 4, 2, 6, 4, 6, 4. Probability that ETF value is divisible by 4 is (3/8) = 0.375

Time Limit: 1,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: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

Code Monk (Number Theory - III)

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?