Add operator and fraction<Apr Circuits>

5

1 votes
Euler's totient function, Hard, Math, Number Theory
Problem

You are given two fractions: 0/1 and 1/2. In each step, you will get two adjacent fractions and you need to add them, if and only if, the denominator is equal to or smaller than the number obtained in that step and write it between those two adjacent fractions.

Example:

Step 1: 0/1,1/2

Step 2: 0/1,1/2

Step 3: 0/1,1/3,1/2 and so on

The add operator is defined as follows:

If (a/b) and (c/d) is added, then the sum is (a+c)/(b+d) which means that their numerators and denominators both are added to each other.

You have to find the kth fraction in the nth step.

Note: You will be given the values of n and k

Input format

First line: Two integers n and k (1<n<=100000 ) where n is the number of steps. It is guaranteed that there is at least k numbers written in nth step.

Output format

Print the answer in the format (int)/(int), like 3/5.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

0/1,1/2 first step

0/1,1/2 second step

0/1,1/3,1/2 third step

0/1,1/4,1/3,1/2 fourth step

0/1,1/5,1/4,1/3,2/5,1/2 fifth step and the fifth fraction is 2/5

Editor Image

?