P1458 [USACO2.1] Ordered Fractions

Input a natural number $n$. For a reduced fraction $a/b$ (a fraction whose numerator and denominator are coprime) that satisfies $1 \le b \le n, 0 \le a/b \le 1$, find all fractions meeting the conditions. Here is an example. When $n=5$, all solutions are: $$\frac01,\frac15,\frac14,\frac13,\frac25,\frac12,\frac35,\frac23,\frac34 ,\frac45,\frac11$$ Given a natural number $n$, write a program to output all solutions in increasing order of their values. Note: 1. The greatest common divisor of $0$ and any natural number is that natural number. 2. “Coprime” means the greatest common divisor of the two natural numbers equals $1$.

A single line containing a natural number $n$.

Each fraction occupies one line, in increasing order.

Constraints For $100\%$ of the testdata, $1 \le n \le 160$. USACO 2.1 Translation from NOCOW. Translated by ChatGPT 5