All pastes #1337928 Raw Edit

Unnamed

public text v1 · immutable
#1337928 ·published 2009-02-15 12:31 UTC
rendered paste body
#include <stdio.h>
#include <math.h>

typedef unsigned long long ull;

ull ucln(ull a,ull b)
{
    ull r = a%b;
    while (r)
    {
         a = b;
         b = r;
         r = a%b;
    }
    
    return b;
}


main()
{
    ull a,b,c,d;
        
    while (scanf("%llu %llu %llu %llu",&a,&b,&c,&d) != -1)        
    {        
        ull p,q,u,a1,c1,minq=-1,minp=-1;
        
        
        u = ucln(a,b);a/=u;b/=u;
        u = ucln(c,d);c/=u;d/=u;
        
        p = a+c;
        q = b+d;        
        
        u = ucln(p,q);          
        p/=u;q/=u;
        
        a1=trunc(1+a*q*1.0/b);
        c1=ceil(c*q*1.0/d-1);
//        printf("q=%lld a1=%lld c1=%lld  ",q,a1,c1);
        minp=p;minq=q;
        
        for (ull i=a1;i<=c1;i++)
        {
            u=ucln(i,q);
            if (minq>q/u)
            {
                minp=i/u;minq=q/u;
            }           
            else if (minq==q/u && minp > i/u)
            {
                minp=i/u;
            }
        }
        
        printf("%llu/%llu\n",minp,minq);
    }
}