GRUPVIVA - Group Viva

no tags 

Today is external viva of computer science subject and Bosky is not at all prepared for it. Adding to his problems, he hasn't reached college yet. Luckily the external examiner was late too. Bosky somehow managed to reach the college before the external examiner arrived but he was still worried because he didn't want to get insulted by external examiner.

The procedure for the conducting of viva is that each student has to sign the attendance register regardless of their given roll number before entering the viva room. Then they will be called individually or in groups of equal students exactly in the same order as they signed in the attendance register. It should be ensured by the internal invigilator that signing in the attendance register by the students has to be done before the external examiner arrives. The viva exam will start immediately only after the arrival of the external examiner. Students were informed that external examiner will arrive exactly after 30 mins. Bosky got some extra time to think how he can save himself from being insulted in front of the external examiner. He looked around and found that there were few students who were in worse condition than he himself was. With his past experience he concluded that on being called in groups the external picks up the most vulnerable student among the group and keeps on insulting and cursing the same student, ignoring the rest. Bosky knew that if he could manage to be in group with a student who is more vulnerable than him then he might get ignored by the external.

When everybody started signing the attendance register, Bosky quickly looked around and spotted such a student and signed after him in the attendance register. He is quite certain now that if he has to give viva in a group in which both of them are present he might save himself from being insulted.

There are "N" students in his class and Bosky knows that external examiner will call everyone in group of "X" students at once,where X can be any number between [1,N] (both ends inclusive). Now he wonders what is the probability that he and his "prey" would be in the same group.

Given total number of students and Bosky's position in the attendance register, your task is to tell what is the probability that Bosky's plan will succeed i.e. he and his [so called] "prey" will be in same group.

More formally you are given two integers N and R ,where 2<=N<=10^9 and 2<=R<=N . You have to find the probability that R and (R-1) will be in the same group if the sequence [1,2,3...N] is divided into group of "X" numbers sequentially i.e [1...N] is divided into groups [1...X],[(X+1)...2*X], [(2*X+1)...3*X] ... [ (X*floor((N-1)/X)+1)...N] , where 1<=X<=N and last group can have less than X numbers.


Input will contain a number T denoting the number of test cases.

Then T test cases follow, each one consisting 2 integers N and R where N is the total strength of the class and R is Bosky's position in the attendance register.


For each test case, output the probability as rational number of form p/q.The greatest common divisor of p and q should be 1.


1<= T <=500

1< N <=10^9

1< R <=N

Sample Input

5 5
6 5

Sample Output 



Case 1: N=5 and R=5

             i.e. Total Students=5 and Bosky's has signed at 5th position

                   his pray signed before him hence he signed at 4th position

   Suppose students are called in group of "X",where 1<=X<=N

   For different values of "X" groups formed are as follow

   For, X=1 

               [ {1},{2},{3},{4},{5} ]


               [ {1,2} , {3,4} , {5} ]


               [ {1,2,3} , {4,5} ]


               [ {1,2,3,4} , {5} ]


               [ {1,2,3,4,5} ]

   We can clearly see that for X=3 and X=5 Bosky's plan will succeed i.e. he and his pray will be in same group. Hence the output is "2/5"

Case 2: Similar to Case 1 where N=6 and R=5

         For, X=1 

               [ {1},{2},{3},{4},{5},{6} ]


               [ {1,2} , {3,4} , {5,6} ]


               [ {1,2,3} , {4,5,6} ]


               [ {1,2,3,4} , {5,6} ]


               [ {1,2,3,4,5}, {6} ]


               [ {1,2,3,4,5,6} ]

   Here Bosky's plan succeeds for X=3,X=5 and X=6. 


   Hence the output is "3/6" ==> "1/2" [Note: Output must be irreducible rational number] 

hide comments
Anubhav Balodhi : 2014-07-07 21:15:44

got tle with näive algo... still getting WA with an apt algo..
never mind, got AC finally ^_^

Last edit: 2014-10-21 12:03:34
P_Quantum: 2014-07-03 19:41:36

nice prblm

J_P: 2014-07-03 09:58:03

nice one.. :)

Bhavik: 2014-05-31 11:43:24

@ankush: int has got nothing to do with was only for speed comparison!
indended algo will easily pass even with lld...try improving whatever present algo u have:)

Last edit: 2014-05-31 11:50:35
Ankush Sharma: 2014-05-31 10:30:46

@Bhavik , tried int but no help.Which algo you have used ?

Bhavik: 2014-05-29 17:14:24

'int' is sufficient!
long long int costed me 0.04 sec but with int(same code) its 0.00 sec

Ankush Sharma: 2014-05-29 06:13:05

Getting TLE,need help !!

raunakrocks: 2014-05-28 21:33:16

Learnt about the logic ..nyce problem

Ahmedali Durga: 2014-05-23 07:52:40

I am getting TLE but i've tried the best optimization possible..

Manish Singh Bisht: 2014-05-12 17:45:10

@Flago: I am glad :)

Added by:Manish Singh Bisht
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64