小于 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。即使循环看起来正确，我也无法理解出了什么问题。任何更好的方法也是受欢迎的。
注意：已超出时间限制

Answer 1

for 循环很好。我很确定 while 循环中出了点问题，即您的条件总是计算为 true。它可能与 -> 含义暗示而不是 (t--(> 有关，我相信这就是你想要的。

更好的方法是实现类似法里序列或斯特恩-布罗科序列的东西。

Answer 2

您可以使用欧拉的全能函数和动态规划。

第 1 步：生成所有素数，直至最大可能值 n。

第 2 步：计算所有1 <= i <= max possible value of n的totient[i]。为此使用动态规划。

• totient[1] = 0

• totient[i] = i - 1 i是否是素数

• totient[i] = totient[i/d] * totient[d]适用于除i的任何d(遍历素数以查找d(

第 3 步。p < q <= i p/q的不可约级分的数量为totient[2] + totient[3] + totient[4] + ... + totient[i](法里序列长度(。在计算图腾时也要计算。

• numberOfFractions[1] = 0

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