Число отдельных фракций меньше 1

Учитывая число N, предлагается найти количество различных фракций, таких, что если приведенная доля равна P/Q (P и Q взаимно простые), то P и Q должен быть <=N. Итак, сначала я придумал этот наивный подход.Число отдельных фракций меньше 1

public static void main (String[] args) throws java.lang.Exception 
    { 
    // your code goes here 
    Scanner sc = new Scanner (System.in); 
    int t = sc.nextInt();//number of test cases 
    while(t-->0){ 
     int n = sc.nextInt();//integer N 
     int count=0; 
     for(int i=1;i<=n;i++){ 
      for(int j=1;j<i;j++){ 
       if(gcd(i,j)==1) 
        count++; 
      } 
     } 
     System.out.println(count); 
    } 
    } 
    public static int gcd(int a,int b){ 
     if(b!=0) 
      return gcd(b,a%b); 
     else 
      return a; 
    }

который был отклонен как TLE. Затем я подумал о предварительном вычислении значений, как было упомянуто N<=1000000. Так что я попытался это:

public static void main (String[] args) throws java.lang.Exception 
    { 
    // your code goes here 
    Scanner sc = new Scanner (System.in); 
    int[] arr = new int[1000001]; 
    arr[0]=0; 
    for(int i=1;i<1000001;i++) 
    { 
     arr[i]=arr[i-1]; 
     for(int j=i-1;j>=0;j--) 
     { 
      if(gcd(i,j)==1) 
       arr[i]++; 
     } 
    } 
    int t = sc.nextInt(); 
    while(t-->0){ 
     int n = sc.nextInt(); 
     System.out.println(arr[n]); 
    } 
    } 
    public static int gcd(int a,int b){ 
     if(b!=0) 
      return gcd(b,a%b); 
     else 
      return a; 
    }

Но теперь она показывает TLE даже для N=1, 2 и 3 тоже. Я не могу понять, что происходит не так, даже если петли кажутся правильными. Любой лучший подход также приветствуется.
ПРИМЕЧАНИЕ: TLE ВРЕМЯ ОГРАНИЧИВАЕТСЯ ПРЕИМУЩЕСТВА

источник

2016-07-26 yobro97

Что TLE значит? Слишком мало усилий? – subrunner

Возможно, вам захочется найти последовательность Farey, например. https://en.wikipedia.org/wiki/Farey_sequence – dmuir

@subrunner TLE превышен лимит времени – yobro97

Для петель в порядке. Я уверен, что в цикле while что-то пойдет не так, т. Е. Ваше состояние всегда оценивает значение true. Это может иметь какое-то отношение к -> означает подразумевать вместо (t -)>, что я уверен, это то, что вы хотите.

Гораздо лучший подход - реализовать что-то вроде Farey Sequence или Stern-Brocot Sequence.

источник

2016-07-26 14:41:25 AlgorithmsX

Я использовал 'while (t -> 0)' в течение длительного времени. Он никогда не вызывал таких ошибок раньше. :( – yobro97

И добавив к этому, предыдущее решение выполнялось без TLE для 'N = 1',' 2' и '3', которое также имеет' t -> 0' – yobro97

. В исходной программе может быть только то, что временная сложность вложенного цикла цикла - это O (n^2), и вы ставите 1000000 in для n. Во второй программе это имеет какое-то отношение к циклу while. Можете ли вы посмотреть, как работает какая-то версия программы, – AlgorithmsX

Вы можете использовать Euler's totient function и динамическое программирование.

Шаг 1: Генерировать все простые числа вплоть до максимально возможного значения n.

Этап 2: Рассчитать totient[i] для всех 1 <= i <= max possible value of n. Для этого используйте динамическое программирование.

totient[1] = 0
totient[i] = i - 1, если i первична
totient[i] = totient[i/d] * totient[d] для любого d, который делит i (цикл над простыми числами, чтобы найти d)

Ste p 3. Число неприводимых фракций p/q с p < q <= i составляет totient[2] + totient[3] + totient[4] + ... + totient[i] (Farey sequence длина). Также вычисляйте при вычислении тотаторов.

numberOfFractions[1] = 0
numberOfFractions[i] = numberOfFractions[i-1] + totient[i]

источник

2016-07-26 15:53:41

Число отдельных фракций меньше 1

ответ

Смежные вопросы