Phi Numbers in Range!

Codeware19: Intra AUST Pr...
Limits 5s, 1.0 GB

In number theory, Euler’s phi function, denoted as ϕ(n)ϕ(n), is an arithmetic function which counts the positive integers less than or equal to PP that are relatively prime to PP. A number XX is relatively prime to PP if GCD(X,P)=1GCD(X,P)=1.For example, if P=10P = 10, then there are 4 numbers, namely 1, 3, 7, 9 which are relatively prime to 10. Therefore, ϕ(10)=4ϕ(10)=4.

In this problem, you have to answer MM number of queries of the form L R K. To answer the queries at first you have to generate an array AA consisting of first NN phi numbers. For example if N=11N=11, then array AA will look like, A={1,1,2,2,4,2,6,4,6,4,10}A=\{1,1,2,2,4,2,6,4,6,4,10\}. For clarity, ϕ(1)=1ϕ(1)=1, ϕ(2)=1ϕ(2)=1, ϕ(3)=2ϕ(3)=2, ϕ(4)=2ϕ(4)=2, ϕ(5)=4ϕ(5)=4, ϕ(6)=2ϕ(6)=2, ϕ(7)=6ϕ(7)=6, ϕ(8)=4ϕ(8)=4, ϕ(9)=6ϕ(9)=6, ϕ(10)=4ϕ(10)=4, ϕ(11)=10ϕ(11)=10.

For each query, you have to print the smallest KK-th distinct phi number in the range LL to RR. Say L=6L = 6, R=11R = 11, K=2K = 2. Let SS denote the set of elements of array AA with its indices between 6 and 11. Then S={2,6,4,6,4,10}S = \{2, 6, 4, 6, 4, 10\}. The smallest 2nd distinct phi number = 4. What if K=3K = 3? Answer is 6.

Notice that if K=5K = 5 then there is no smallest KK-th distinct phi number in that range. In such case, you have to print “No Distinct Phi Number” (w/o quotes).


At first, there will be an integer TT (1T101 ≤ T ≤ 10), which is the number of test cases. For each case, you will be given two positive integers NN and MM (1N,M1051 ≤ N, M ≤ 10^5) that are the number of phi numbers to be generated at first and the number of queries. Then there will be MM lines each containing three numbers L R K (1LRN,1KN1 ≤ L ≤ R ≤ N, 1 ≤ K ≤ N).


For each case print the case number in the first line like "Case x:" where xx is the number of the test case. Then output the smallest KK-th distinct phi number or "No Distinct Phi Number" (w/o quotes) for each query in a new line.


11 4
4 6 1
6 11 2
2 7 3
4 6 4
Case 1:
No Distinct Phi Number


Login to submit.



72% Solution Ratio
MU_ResplendenceEarliest, Sep '19
Yasir_ArafatFastest, 0.4s
random_shuffleLightest, 26 MB
kzvd4729Shortest, 1834B
Toph uses cookies. By continuing you agree to our Cookie Policy.