Add operator and fraction<Apr Circuits>
Practice
5 (1 votes)
Euler's totient function
Hard
Math
Number theory
Problem
89% Success 467 Attempts 50 Points 1s Time Limit 256MB Memory 1024 KB Max Code

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.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:20
4 votes
Tags:
MathematicsOpenApprovedEasyMathamatics
Points:50
3 votes
Tags:
Totient FunctionNumber theoryEuler's totient functionMathematicsNumber TheoryMath
Points:20
193 votes
Tags:
AlgorithmsApprovedEasyImplementationOpen