Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Phi Numbers in Range!

Limits 5s, 1.0 GB

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

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

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

Notice that if K = 5 then there is no smallest k-th distinct phi number in that range. In such case, you have to print No Distinct Phi Number.


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


For each case print the case number in the first line like “Case x:” where x is the number of the test case. Then output the smallest K-th distinct phi number or “No Distinct Phi Number” 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



67% Solution Ratio

MU_ResplendenceEarliest, 5M ago

random_shuffleFastest, 0.8s

random_shuffleLightest, 26 MB

kzvd4729Shortest, 1834B


Login to submit

Related Contests