Finding a irreducible fraction

Given a positive integer n , it is asked to find the probability that one can pick two numbers A and B from the set [1...n] , such that the GCD of A and B is B . So my approach was to calculate number of pairs such that one is divisible by another. And the answer was expected to be in irreducible fraction form .
EXAMPLE:
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);

And my hcf function was:

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

But the compiler message was time-out. I think there may be some problem with the hcf function or there is a better and efficient method for finding the irreducible fraction. Since it was successful for smaller inputs, I think there is most probably an efficient method for finding the irreducible fraction form. Any suggestions?

---

Your hcf function is not too slow. Instead, the problem is that you have a for loop which iterates O(n) times, which is quite a lot when n = 10^9 . You can get it down to O(sqrt(n)) by only counting cases where B <= sqrt(A) . That will give you about half of the cases, because usually exactly one of B and A/B is smaller than sqrt(A) . The only exception is you have to account for cases when B * B = A .

链接地址: http://www.djcxy.com/p/35730.html

上一篇: 使用ngUpgrade和路由引导一个Angular 2 rc.6混合应用程序

下一篇: 找到一个不可简化的部分