Fraction Subtraction
Time limit1sMemory limit128 MB
For each fraction b/n, list every numerator a and denominator m with a >= 0, m > 0 such that the wrong subtraction (a-b)/(m-n) equals the correct one a/m - b/n.
- Level
Medium7 of 10
- Topics
- Number theory, Math, Implementation, Sorting
- Solved
- No attempts yet
Problem
In elementary school, students learn how to subtract fractions. However, one student does the subtraction the wrong way: they subtract the denominators from each other and the numerators from each other.
For example, consider the following subtraction.
The student subtracts denominator from denominator and numerator from numerator, computing it like this:
Surprisingly, there are cases where this incorrect method gives the same result as the correct subtraction.
Given a fraction , write a program that finds every and satisfying the equation below, where and .
Input
The input consists of several test cases. Each test case is a single line containing two integers and . ()
The last line of the input contains two zeros, and this line is not processed.
Output
For each test case, print on one line every fraction that satisfies the condition. Print the fractions in increasing order of value; if two fractions have the same value, print the one with the smaller numerator first.
Each fraction must be printed in the form a/m, with no spaces before or after the /. Print a single space between consecutive fractions on the same line.