Submission #146666

#	Time	Username	Problem	Language	Result	Execution time	Memory
146666		pichulia	분수 (KPI13_fractions)	C++11	0 / 1	2 ms	256 KiB

fractions

#include<stdio.h>
unsigned long long int find_r(unsigned long long int x, unsigned long long int b)
{
    unsigned long long int l,r,mid;
    l=2; r=b;
    while(l<r)
    {
        mid = (l+r)/2;
        if((x*mid/b) < mid-1) r = mid;
        else l=mid+1;
    }
    return l-2;
}
unsigned long long int gcd(unsigned long long int p, unsigned long long int q)
{
    while(p%q){
        unsigned long long int t=p%q;
        p=q;
        q=t;
    }
    return q;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        unsigned long long int a,b,c,d;
        unsigned long long int k,s;
        scanf("%llu %llu %llu %llu",&a,&b,&c,&d);
        unsigned long long int x,y;
        unsigned long long int p,q,r;
        unsigned long long int g;
        g = gcd(a,b);
        a/=g;
        b/=g;
        g = gcd(c,d);
        c/=g;
        d/=g;
        k = a/b;
        if(c/d > k)
        {
            printf("%llu 1\n",k+1);
        }
        else
        {
            a %= b;
            c %= d;
        y=1;
        while(1)
        {
            p=d+(a*y/b)*d;
            q=c*y;
            if(p<q)break;
            r = a*y%b;
            s = find_r(r,b);
            //printf("%llu %llu %llu   %llu %llu  %llu\n",p,q,p-q,r,s, (p+(d-c)*s-q)/c);
            y += s+(p+(d-c)*s-q)/c+1;
        }
        x = a*y/b+1+k*y;
        printf("%llu %llu\n",x,y);
        }
    }
}

Compilation message (stderr)

fractions.cpp: In function 'int main()':
fractions.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&t);
     ~~~~~^~~~~~~~~
fractions.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%llu %llu %llu %llu",&a,&b,&c,&d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 1