找到一个不可简化的部分
给定一个正整数n ，它要求找到一个可以选择两个号码的概率A和B从集合[1...n]使得GCD的A和B是B 。 所以我的方法是计算一对可以被另一个整除的数量。 预计答案是不可简化的分数形式 。
例：
1 2 3
OUTPUT：
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函数可能存在一些问题，或者有一种更好和更有效的方法来找到不可hcf的部分。 由于它对较小的投入是成功的，我认为最有可能的一种找到不可简化的分数形式的有效方法。 有什么建议么？
您的hcf功能不是太慢。 相反，问题是你有一个迭代O(n)次的for循环，当n = 10^9时这是相当多的。 您只需对B <= sqrt(A)情况进行计数，就可以将其降至O(sqrt(n)) B <= sqrt(A) 。 这会给你一半左右的情况，因为B和A/B通常只有一个小于sqrt(A) 。 唯一的例外是，当B * B = A时，你必须考虑情况。