import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; class Ideone { { { while (in.hasNextInt()) { farey(in.nextInt()); } } } static void farey(int m) { ArrayList<String> farey = new ArrayList<>(); stack.push(fraction(1, 1)); stack.push(fraction(0, 1)); while (true) { long l = stack.pop(); farey.add(fractionToString(l)); if (stack.isEmpty()) break; while (true) { long r = stack.peek(); if (!test(l, r, m)) break; stack.push(l + r); } } } static long fraction(int n, int d) { return (long) n << 32 | d; } static boolean test(long l, long r, int m) { return (l & 0xFFFFFFFFL) + (r & 0xFFFFFFFFL) <= m; } { return (l >>> 32) + "/" + (l & 0xFFFFFFFFL); } { long[] array = new long[64]; int ptr; void push(long l) { array[ptr++] = l; } long pop() { return array[--ptr]; } long peek() { return array[ptr - 1]; } boolean isEmpty() { return ptr == 0; } } }
3 5 8
Farey[3] => [0/1, 1/3, 1/2, 2/3, 1/1] Farey[5] => [0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1] Farey[8] => [0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1]