fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Scanner;
  4.  
  5. class Ideone
  6. {
  7.     public static void main(String[] args)
  8.     {
  9.         try (Scanner in = new Scanner(System.in))
  10.         {
  11.             while (in.hasNextLine())
  12.             {
  13.                 String line = in.nextLine();
  14.                 if (line.isEmpty())
  15.                 {
  16.                 	System.out.println();
  17.                 	continue;
  18.                 }
  19.  
  20.                 String[] s = line.split("[\\s,]");
  21.                 if (s.length == 1) farey(Integer.parseInt(s[0]));
  22.                 if (s.length == 2) farey(Integer.parseInt(s[0]), Integer.parseInt(s[1]));
  23.             }
  24.         }
  25.     }
  26.  
  27.     static void farey(int m)
  28.     {
  29.         ArrayList<String> farey = new ArrayList<>();
  30.         Stack stack = new Stack();
  31.         stack.push(fraction(1, 1));
  32.         stack.push(fraction(0, 1));
  33.  
  34.         while (true)
  35.         {
  36.             long l = stack.pop();
  37.             farey.add(fractionToString(l));
  38.             if (stack.isEmpty()) break;
  39.  
  40.             while (true)
  41.             {
  42.                 long r = stack.peek();
  43.                 if (!test(l, r, m)) break;
  44.                 stack.push(l + r);
  45.             }
  46.         }
  47.  
  48.         System.out.printf("Farey[%d] => %s%n", m, farey);
  49.     }
  50.  
  51.     static void farey(int n, int k)
  52.     {
  53.         int c = 0;
  54.         Stack stack = new Stack();
  55.         stack.push(fraction(1, 1));
  56.         stack.push(fraction(0, 1));
  57.  
  58.         while (true)
  59.         {
  60.             long l = stack.pop();
  61.             if (++c == k)
  62.             {
  63.                 System.out.printf("Farey[%d,%d] -> %s%n", n, k, fractionToString(l));
  64.                 break;
  65.             }
  66.             if (stack.isEmpty()) break;
  67.  
  68.             while (true)
  69.             {
  70.                 long r = stack.peek();
  71.                 if (!test(l, r, n)) break;
  72.                 stack.push(l + r);
  73.             }
  74.         }
  75.     }
  76.  
  77.  
  78.     static long fraction(int n, int d)
  79.     {
  80.         return (long) n << 32 | d;
  81.     }
  82.  
  83.     static boolean test(long l, long r, int m)
  84.     {
  85.         return (l & 0xFFFFFFFFL) + (r & 0xFFFFFFFFL) <= m;
  86.     }
  87.  
  88.     static String fractionToString(long l)
  89.     {
  90.         return (l >>> 32) + "/" + (l & 0xFFFFFFFFL);
  91.     }
  92.  
  93.  
  94.     static class Stack
  95.     {
  96.         long[] array = new long[64];
  97.         int ptr;
  98.  
  99.         void push(long l)
  100.         {
  101.             if (ptr == array.length) array = Arrays.copyOf(array, array.length * 2);
  102.             array[ptr++] = l;
  103.         }
  104.  
  105.         long pop()
  106.         {
  107.             return array[--ptr];
  108.         }
  109.  
  110.         long peek()
  111.         {
  112.             return array[ptr - 1];
  113.         }
  114.  
  115.         boolean isEmpty()
  116.         {
  117.             return ptr == 0;
  118.         }
  119.     }
  120. }
  121.  
Success #stdin #stdout 0.1s 4386816KB
comments (?)
stdin
copy 
5,4
5

24,17
24

1000000,5000000
stdout
copy 
Farey[5,4] -> 1/3
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[24,17] -> 2/21
Farey[24] => [0/1, 1/24, 1/23, 1/22, 1/21, 1/20, 1/19, 1/18, 1/17, 1/16, 1/15, 1/14, 1/13, 1/12, 2/23, 1/11, 2/21, 1/10, 2/19, 1/9, 2/17, 1/8, 3/23, 2/15, 3/22, 1/7, 3/20, 2/13, 3/19, 1/6, 4/23, 3/17, 2/11, 3/16, 4/21, 1/5, 5/24, 4/19, 3/14, 5/23, 2/9, 5/22, 3/13, 4/17, 5/21, 1/4, 6/23, 5/19, 4/15, 3/11, 5/18, 2/7, 7/24, 5/17, 3/10, 7/23, 4/13, 5/16, 6/19, 7/22, 1/3, 8/23, 7/20, 6/17, 5/14, 4/11, 7/19, 3/8, 8/21, 5/13, 7/18, 9/23, 2/5, 9/22, 7/17, 5/12, 8/19, 3/7, 10/23, 7/16, 4/9, 9/20, 5/11, 11/24, 6/13, 7/15, 8/17, 9/19, 10/21, 11/23, 1/2, 12/23, 11/21, 10/19, 9/17, 8/15, 7/13, 13/24, 6/11, 11/20, 5/9, 9/16, 13/23, 4/7, 11/19, 7/12, 10/17, 13/22, 3/5, 14/23, 11/18, 8/13, 13/21, 5/8, 12/19, 7/11, 9/14, 11/17, 13/20, 15/23, 2/3, 15/22, 13/19, 11/16, 9/13, 16/23, 7/10, 12/17, 17/24, 5/7, 13/18, 8/11, 11/15, 14/19, 17/23, 3/4, 16/21, 13/17, 10/13, 17/22, 7/9, 18/23, 11/14, 15/19, 19/24, 4/5, 17/21, 13/16, 9/11, 14/17, 19/23, 5/6, 16/19, 11/13, 17/20, 6/7, 19/22, 13/15, 20/23, 7/8, 15/17, 8/9, 17/19, 9/10, 19/21, 10/11, 21/23, 11/12, 12/13, 13/14, 14/15, 15/16, 16/17, 17/18, 18/19, 19/20, 20/21, 21/22, 22/23, 23/24, 1/1]

Farey[1000000,5000000] -> 14/848963
https://ideone.com/9AXdRV
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!