java - 寻找不可约分数

Question

给定一个正整数n，要求找出从集合A和B中选出两个数字的概率[1...n]，使得A和B的GCD为B。所以我的方法是计算对的数量，使得一个可以被另一个整除。答案应该是不可约分数形式。
示例:
1 2 3
输出:
1/1 3/4 5/9

long n = sc.nextLong();
long sum=0;
for(long i=1;i<=n/2;i++)
    sum+=(n/i)-1;
 long tot = n*n;
 sum+=n;
 long bro = hcf(tot,sum);
 sum/=bro;
 tot/=bro;
 System.out.print(sum+"/"+tot);

我的 hcf 函数是:

public static long hcf(long n1,long n2)
{
    if (n2!=0)
        return hcf(n2, n1%n2);
    else 
        return n1;
}

但是编译器消息超时。我认为 hcf 函数可能存在一些问题，或者有更好更有效的方法来查找不可约分数。由于它对于较小的输入是成功的，我认为很可能有一种有效的方法来找到不可约的分数形式。有什么建议吗？

Answer 1

你的 hcf功能不是太慢。相反，问题是你有一个迭代 O(n) 的 for 循环次，当n = 10^9时，这是相当多的.你可以把它归结为 O(sqrt(n))通过只计算 B <= sqrt(A) 的情况.这将为您提供大约一半的案例，因为通常恰好是 B 中的一个。和 A/B小于 sqrt(A) .唯一的异常(exception)是您必须考虑 B * B = A 时的情况。 .