分数の数が1より小さい場合

Question

数値がNである場合、分数がP/Q（PとQはコプライム）の場合、PとQ <=Nである必要があります。 だから私はこの素朴なアプローチを思いついた。

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; 
    } 

しかし、今では、あまりにも、N=1、2と3のためのTLEを示しています。ループが正しいように見えても何がうまくいかないのか理解できません。より良いアプローチも歓迎します。
注：TLEは制限時間を超えています

Answer 1

forループは正常です。 whileループで何かが間違っている、つまり条件が常にtrueに評価されていることを確認しています。それは、（t - ）>の代わりに意味を持つ意味があるかもしれません。あなたが望むのは確かです。

より良いアプローチは、Farey Sequenceまたは​​のようなものを実装することです。

Answer 2

Euler's totient functionと動的プログラミングを使用できます。

ステップ1：可能な最大値までのすべての素数を生成します。

ステップ2：すべて1 <= i <= max possible value of nについてtotient[i]を計算します。これには動的プログラミングを使用します。

• totient[1] = 0

• totient[i] = i - 1iは

マリー（dを見つけるために、素数をループ）iを分割する任意dの主要

totient[i] = totient[i/d] * totient[d]ある場合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]