All Tracks>Math> Number Theory> Totient Function> Problem
Monk And ETF
★★★★★

4.5

44 votes
Approved, Euler's totient function, Math, Medium, Open, Ready, Sieve
Problem

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
Time Limit: 1
Memory Limit: 256
Source Limit:
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

Contributers:
Editor Image

?