寻找不可减少的部分

Question

给定一个正整数n,它要求找到一个可以选择两个号码的可能性A,并B从集合[1...n],使得GCD中A和B的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)。唯一的例外是您必须考虑以下情况B * B = A：